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.*;

public class Little_Elephant_and_Numbers {

    static boolean ok(int d, int n) {
        char[] D = (d + "").toCharArray();
        char[] N = (n + "").toCharArray();

        for (int i = 0; i < D.length; i++) {
            for (int j = 0; j < N.length; j++) {
                if (D[i] == N[j])
                    return true;
            }
        }
        return false;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int count = 0;
        // ArrayList<Integer> divisors = new ArrayList<Integer>();
        if (n == 1) {
            // divisors.add(1);
            if (ok(1, n))
                count++;
        } else {
            int squr = (int) Math.sqrt(n);
            for (int i = 1; i <= squr; i++) {
                if (n % i == 0) {
                    if (ok(i, n))
                        count++;
                    if (ok((int) (n / i), n))
                        count++;
                    // divisors.add(i);
                    // divisors.add((int) (n / i));
                }
            }
            if (n == squr * squr) {
                if (ok(squr, n))
                    count--;
                // divisors.add(i);
            }
        }
        
        System.out.println(count);
    }
}