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

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		String NN = N+"";
		int sqrt = (int) (Math.sqrt(N)+1);
		long ans = 1;
		
		if(N!=1)ans+=check(NN,"1");
		for(int a=2;a<sqrt;a++){
			if(N%a==0){
				ans+=check(NN,""+a);
				if(N/a !=a)ans+=check(NN,""+(N/a));
			}
		}
		System.out.println(ans);
	}

	private static long check(String n,String m) {
		for(int a=0;a<n.length();a++)
			for(int b=0;b<m.length();b++)
				if(n.charAt(a)==m.charAt(b))return 1;
		
		return 0;
	}

}
