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 ElephantAndNumbers {
	public ElephantAndNumbers (){
		Scanner stream = new Scanner (System.in);
		int n = stream.nextInt() ;
		System.out.println(number(n));
	}
	public int number (int n){
		String num = String.valueOf(n);
		boolean [] arr = new boolean [10];
		for (int i = 0 ; i < num.length() ; i++){
			arr[ num.charAt(i) - '0' ] = true ;
		}
		int counter = 0;
		for (int i = 1 ; i*i<= n ; i++){
			if (i*i == n){
				String temp = String.valueOf(i);
				for (int j =0 ; j < temp.length() ; j++){
					if (arr[temp.charAt(j)-'0']){
						counter++ ;
						break ;
					}
				}
			}else if (n%i == 0){
				String temp1 = String .valueOf(i);
				String temp2 = String.valueOf(n/i);
				for (int j =0 ; j < temp1.length() ; j++){
					if (arr[temp1.charAt(j)-'0']){
						counter++ ;
						break;
					}
				}
				for (int j =0 ; j < temp2.length() ; j++){
					if (arr[temp2.charAt(j)-'0']){
						counter++ ;
						break ;
					}
				}
			}
		}
		return counter ;
	}
	public static void main (String [] args){
		new ElephantAndNumbers() ;
	}
}