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 B {

    private static boolean isPrime(int x) {
        for (int i = 2; i <= x / i; i++)
            if (x % i == 0)
                return false;
        return true;
    }

    private static void get() {
        Scanner scan = new Scanner(System.in);

        int n = scan.nextInt();
        int t = n;
        if (n == 1){
            System.out.println(1);
            return;
        }
        if (isPrime(n)) {
            String x = "" + n;
            for (int i = 0; i < x.length(); i++) {
                if (x.charAt(i) == '1') {
                    System.out.println(2);
                    return;
                }
            }
            System.out.println(1);
            return;
        } else {
            int[] array = new int[10000];
            int p = 0;
            int m = (int) Math.ceil(Math.sqrt(n));
            for (int i = 2; i <= m; i++)
                if (n % i == 0) {
                    array[p] = i;
                    p++;
                    if (i != m) {
                        array[p] = n / i;
                        p++;
                    }
                }
            int d = 0;
            for (int i = 0; i < p; i++) {
                if (m3ana(t, array[i])) {
                    d++;
                }
            }
            String x = "" + t;
            for (int i = 0; i < x.length(); i++) {
                if (x.charAt(i) == '1') {
                    System.out.println(2 + d);
                    return;
                }
            }
            System.out.println(d + 1);
        }

    }

    private static boolean m3ana(int n, int t) {
        String a1 = "" + n;
        String a2 = "" + t;
        for (int i = 0; i < a1.length(); i++)
            for (int j = 0; j < a2.length(); j++)
                if (a1.charAt(i) == a2.charAt(j))
                    return true;
        return false;
    }

    public static void main(String[] args) {
        get();
    }
}
