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.Arrays;
import java.util.Scanner;

public class TestSolution{

	public static void main (String args[]){

		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		if(n == 1) System.out.println(1);
		else{
			String sn[] = (n+"").split("");
			int c = 0;
			int l = (int)Math.sqrt(n);
			for(int i=1; i<=l; i++){
	            if(n%i==0) {
	            	int m = n/i;
	            	
	            	String si = i+"";
	            	for (int j = 0; j < sn.length; j++) {	
						if(si.contains(sn[j])){
							c++;
							break;
						}
					}
	            	if(i!=m){
		            	String sm = m+"";
		            	for (int j = 0; j < sn.length; j++) {	
							if(sm.contains(sn[j])){
								c++;
								break;
							}
						}
	            	}
	            	
	            }
	        }
			System.out.println(c);
		}
		scanner.close();
}
}