The Little Elephant loves numbers. 

He has a positive integer x. The Little Elephant wants to find the number of positive integers d, such that d is the divisor of x, and x and d have at least one common (the same) digit in their decimal representations. 

Help the Little Elephant to find the described number.

Input

A single line contains a single integer x (1 ≤ x ≤ 109).

Output

In a single line print an integer — the answer to the problem.

Examples

Input

1


Output

1


Input

10


Output

2
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Collections;
import java.util.Scanner;
import java.util.Vector;


public class Main {

    
    public static void main(String[] args) {
        Scanner in=new Scanner(new InputStreamReader(System.in));
        PrintWriter out=new PrintWriter(System.out);
        String s=in.nextLine();
        int n=Integer.parseInt(s);
        s="[0-9]{0,}["+s+"]{1,}[0-9]{0,}";
        int count=0;
            for(int i=1; i<=Math.sqrt(n); i++){
                if(n%i==0){
                    if(String.valueOf(i).matches(s))
                        count++;
                    int j=n/i;
                    if(j!=i && n%j==0 && String.valueOf(j).matches(s)){
                        count++;
                    }
                }
            }
        out.println(count);
        out.close();
    }

}
