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

    public static void main(String args[]) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        String s = String.valueOf(n);
        int c = 0;
        int[] a = new int[10];
        for (int i = 0; i < s.length(); i++) {
            ++a[s.charAt(i) - '0'];
        }
        for (int i = 1; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                String k = String.valueOf(i);
                for (int j = 0; j < k.length(); j++) {
                    if (a[k.charAt(j) - '0'] >= 1) {
                        ++c;
                        break;
                    }
                }
                if (n / i != i) {
                    String p = String.valueOf(n / i);
                    for (int j = 0; j < p.length(); j++) {
                        if (a[p.charAt(j) - '0'] >= 1) {
                            ++c;
                            break;
                        }
                    }
                }

            }
        }
        System.out.println(c);
    }

}
