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 {

    Scanner in;

    public int check(String s1, String s2) {
        int cnt = 0;
        for (int i = 0; i < s1.length(); i++) {
            for (int j = 0; j < s2.length(); j++) {
                if (s1.charAt(i) == s2.charAt(j)) {
                    return 1;
                }
            }
        }
        return cnt;
    }

    public void run() {
        in = new Scanner(System.in);
        int N = in.nextInt();

        if (N == 1) {
            System.out.println(1);
            return;
        }
        int counter = 2;
        String s1 = "", s2 = "", s3 = String.valueOf(N);

        if (check("1", s3) != 1) {
            --counter;
        }

        for (int i = 2; i <= (int) Math.sqrt(N); i++) {
            if (N % i == 0) {
                s1 = String.valueOf(i);
                s2 = String.valueOf(N / i);

                if (i != (N / i)) {
                    if (check(s1, s3) == 1) {
                        counter++;
                    }
                    if (check(s2, s3) == 1) {
                        counter++;
                    }
                } else {
                    if (check(s1, String.valueOf(N)) == 1) {
                        counter++;
                    }

                }

            }
        }

        System.out.println(counter);
    }

    public static void main(String[] args) {
        new Main().run();
    }
}
