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 Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int sum = 0;
		if(n==1)	System.out.println(1);
		else{
			sum=1;
			String s = String.valueOf(n);
			if(s.contains("1"))	sum++;
			
			for(int i = 2;  i<=Math.sqrt(n);i++){
				if(n%i==0){
					String s1 = String.valueOf(n);
					String s2 = String .valueOf(i);
					String s3 = String .valueOf(n/i);
						if(same(s1,s2)){
						
						sum++;
					}
					if(n/i !=i &&same(s1,s3)){
						sum++;
					}
					
					
				}
				
			}
			System.out.println(sum);
		}
	}
	
	public static boolean same(String s1,String s2){
		for(int i = 0 ; i < s1.length();i++){
			for(int j = 0 ;j<s2.length();j++){
				if(s1.charAt(i)==s2.charAt(j)){
					return true;
				}
			}
		}
		return false;
	}

}


 				  		  	 		 						 	 	