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

public class Bedit {

    static boolean in(int q, boolean[] mark) {            
        while(q > 0) {
            if(mark[q % 10]) {
                return true;
            }
            q /= 10;
        }
        return false;
    }

    public static int edit(int n) {
    
        boolean[] mark = new boolean[10];
        int p = n;
        while(p > 0) {
            mark[p % 10] = true;
            p /= 10;
        }        

        int ans = 0;

        int m = (int) Math.sqrt(n);
        for(int i = 1; i <= m; ++ i) {            
            if(n % i == 0) {
                if(in(i, mark)) {
                    ans += 1;
                }
                if(in(n / i, mark) && i * i != n) ans += 1;
            }
        }

        return ans;

    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        System.out.println(edit(n));
    }
}
