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

	static String n;
	static int m;
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {

		long s = System.currentTimeMillis();
		Scanner sc = new Scanner(System.in);
        n = sc.nextLine();
        m = Integer.parseInt(n);
        
        int d = 1;
        int c=0;
        while (d*d<=m){
        	
        	if (m%d==0){
        		if(d(d)){
        			c++;
        		}
        		if (m/d!=d&&d(m/d)){
        			c++;
        		}
        	}
        	d++;
        }
        System.out.println(c);
        //System.out.println(System.currentTimeMillis()-s);
	}
        
    static boolean d(int d){
    	String ds = String.valueOf(d);
    	for (int i=0;i<ds.length();i++){
    		if (n.contains(Character.toString(ds.charAt(i)))){
    			return true;
    		}
    	}
    	return false;
    }

}