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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;


public class main {

    /**
     * @param args
     * @throws IOException 
     * @throws NumberFormatException 
     */
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        HashSet<Integer> d = new HashSet<Integer>();
        int sq = (int) (Math.sqrt(n)+10);
        for (int i = 1; i < sq; i++) {
            if(n%i==0){d.add(i);d.add(n/i);}
        }
        boolean [][] g = chars(d);
        boolean [] c = cc(n);
        boolean [] res = new boolean[d.size()];
        for (int i = 0; i < c.length; i++) {
            if(!c[i])continue;
            for (int j = 0; j < res.length; j++) {
                res[j]|=g[j][i];
            }
        }
        int r = 0;
        for (int i = 0; i < res.length; i++) {
            if(res[i])r++;
        }
        System.out.println(r);
    }

    private static boolean[] cc(int n) {
        // TODO Auto-generated method stub
        boolean[] c = new boolean[10];
        while(n!=0){
            c[n%10]=true;
            n/=10;
        }   
        return c;
    }

    private static boolean[][] chars(HashSet<Integer> d) {
        // TODO Auto-generated method stub
        boolean[][] c = new boolean[d.size()][10];
        int next=0;
        for (Integer i : d) {
            int x = i.intValue();
            while(x!=0){
                c[next][x%10]=true;
                x/=10;
            }
            next++;
        }
                
        return c;
    }

}
