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.*;
import java.util.*;
import java.math.*;

public class Main {
    static StringTokenizer st;
    static PrintWriter out = new PrintWriter(System.out,true);
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        int x = readInt();
        int c = 0;
        for(int i = 1;i*i <= x;i++) {
            if(x % i == 0) {
                if(func(x,i)) c++;
                if(x / i != i && func(x,x/i)) c++;
            }
        }
        out.println(c);
    }

    public static boolean func(int x, int n) {
        int[] dig = new int[10];
        while(x != 0) {
            dig[x%10]++;
            x /= 10;
        }
        while(n != 0) {
            if(dig[n%10] > 0) return true;
            n /= 10;
        }
        return false;
    }

    public static int readInt() throws Exception {
        if(st == null || !st.hasMoreTokens()) st = new StringTokenizer(in.readLine());
        return Integer.parseInt(st.nextToken());
    }
}