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

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner input = new Scanner(System.in);
		int  n = input.nextInt();
		int counter=0;
		String p1 = Long.toString(n);
		for(int i=1;i*i<=n;i++){
			if(n%i==0 && i<n/i && check(n,n/i))counter++;
			if(n%i==0 && i<=n/i && check(n,i))counter++;
		}
		//System.out.println(check("15","5"));
		System.out.println(counter);
		
	}
	
	private static boolean check( int p1,int  p2){
		String s1 = ""+p1;
		String s2 = ""+p2;
		for(int i=0; i<s2.length();i++){
			int p=-1;
			p = s1.indexOf(s2.substring(i,i+1));
			if(p!=-1)return true;
		}
		return false;
	}

}
