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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int x = sc.nextInt();
        
        boolean b [] = new boolean[10];
        
        int x2 = x;
        while(x2 > 0) {
            b[x2%10]=true;
            x2=x2/10;
        }
        
        int lim = (int) Math.sqrt(x);
        int count = 0;
        
        for(int i = 1; i<=lim; ++i) {
            
            if(x % i == 0) {
                boolean found = false;
                int i2=i;
                while(!found && i2 > 0) {
                    found = b[i2%10];
                    i2 = i2/10;
                }
                
                if(found)
                    ++count;
                
                i2 = x / i;
                
                if(i2 != i) {
                    found = false;
                    
                    while(!found && i2 > 0) {
                        found = b[i2%10];
                        i2 = i2/10;
                    }
                    
                    if(found)
                        ++count;
                }
                
            }
            
            
            
        }
        
        System.out.println(count);
    }

}
