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 {
    public static void main(String[] args) {
        Task ts = new Task();
        ts.solve();
    }
}

class Task {
    public void solve() {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int k = 0;
        for(int i = 1; i <= Math.sqrt(x); i++) {
            if(x % i == 0) {
                if(check(x,i)) k++;
                if(i != x / i && check(x,x / i)) k++;
            }
        }
        System.out.print(k);
    }
    boolean check(int a, int b) {
        String as = String.valueOf(a);
        String bs = String.valueOf(b);
        for(int i = 0; i < as.length(); i++) {
            for(int j = 0; j < bs.length(); j++) {
                if(as.charAt(i) == bs.charAt(j)) return true;
            }
        }
        return false;
    }
};
