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

	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		sc.close();
		HashSet<String> factors = new HashSet<String>();
		for (int i = 1; i <= Math.sqrt(num); i++)
			if (num % i == 0)
			{
				factors.add(i + "");
				factors.add(num / i + "");
			}
		String number = num + "";
		int counter = 0;
		for (String factor : factors)
			for (int i = 0; i < factor.length(); i++)
				if (number.contains(factor.substring(i, i + 1)))
				{
					counter++;
					break;
				}
		System.out.println(counter);
	}

}
