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 B {
    static int cnt;
    public static void main(String[] args){
        Scanner reader = new Scanner(System.in);
        int x = reader.nextInt();
        int cap = (int)Math.sqrt(x);
        
        for(int i = 1; i <= cap; i++){
            if(x%i == 0){
                check(x,i);
                if(x/i != i)
                    check(x,x/i);
            }
        }
        
        System.out.println(cnt);
    }
    
    public static void check(int a, int b){
        boolean[] d = new boolean[10];
        int x = a;
        while(x > 0){
            d[x%10] = true;
            x /= 10;
        }
        
        x = b;
        while(x > 0){
            if(d[x%10]){
                cnt++;
                return;
            }
            x /= 10;
        }
    }
}