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

public class C {
	
	static boolean digitoComum(long a, long b){
		String sA=a+"";
		String sB=b+"";
		
		for(char c1: sA.toCharArray()){
			for(char c2: sB.toCharArray()){
				if(c1==c2)return true;
			}
		}
		
		return false;
		
	}
	
	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		
		long x= sc.nextLong();
		
		
		ArrayList<Long>divizores= new ArrayList<>();
		
		for(long i=1;i<=Math.sqrt(x);i++){
			if(x%i==0){
				divizores.add((long) i);
				if((x/i)!=i)divizores.add((long)(x/i));
			}
		}
		long resp=0;
		for(Long l:divizores){
			if(digitoComum(x, l.longValue())){resp++;}
		}
		System.out.println(resp);
	}

}
