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.*;

public class Contest136B
{
	public Contest136B()
	{
		Scanner in = new Scanner(System.in);
		
		Integer num = Integer.valueOf(in.nextLine());
		
		HashSet<Integer> digits = new HashSet<Integer>();
		int temp = num;
		while(temp > 0)
		{
			digits.add(temp % 10);
			temp /= 10;
		}
		
		ArrayList<Integer> factors = new ArrayList<Integer>();
		
		for(int x = 1; x <= Math.pow(num, 0.5); x++)
		{
			if(num % x == 0)
			{
				factors.add(x);
				if(x != Math.pow(num, 0.5))
					factors.add(num / x);
			}
		}
		
		int total = 0;
		
		for(int x = 0; x < factors.size(); x++)
		{
			int a = factors.get(x);

			while(a > 0)
			{
				HashSet<Integer> tempset = cloneHash(digits);
				int size = tempset.size();
				tempset.add(a % 10);
				if(tempset.size() == size)
				{
					total++;
					a = 0;
				}
				a /= 10;
			}
			
		}
		
		System.out.println(total);
	}
	
	public HashSet<Integer> cloneHash(HashSet<Integer> a)
	{
		HashSet<Integer> result = new HashSet<Integer>();
		Iterator it = a.iterator();
		while(it.hasNext())
			result.add((Integer) it.next());
		return result;
	}
	
	public static void main(String[] args)
	{
		new Contest136B();
	}
}
