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.util.Scanner;


public class Main {

    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int x=(int)(Math.pow(n, 0.5));
        int res=0;
        for (int i = 1; i <= x; i++) {
            if(n%i==0){
                res+=contains(n, i);
                if(i*i!=n){
                    res+=contains(n, n/i);
                }
            }
        }
        System.out.println(res);
    }
    
    public static int contains(int a,int b){
        String x=a+"";
        String y=b+"";
        for (int i = 0; i < y.length(); i++) {
            if(x.contains(y.charAt(i)+"")){
                return 1;
            }
        }
        return 0;
    }
}
