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.*;
public class LittleElephantNumber_221B {
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int x = in.nextInt();
        String xx = x+"";
        int ans = 0;
        if(xx.contains("1")) 
            ans++;
        if (x!=1)  //+1 cause it's itself 
            ans++;
        
        for (int i = 2; i*i <= x;i++)
            if (x%i == 0) {
                ans+= digit(i, xx);
                if (x/i!=i) {
                    ans+= digit(x/i, xx);
                }
            }
        System.out.println(ans);
        //System.out.println("larger contain smaller".contains(t));
    }
    static int digit (int a, String xx) {
        char[] aa = (a+"").toCharArray();
        for(int j = 0; j<aa.length; j++)
            if(xx.contains(aa[j]+"")) 
                return 1;
        return 0;
    }
}
