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 Test {
	
	public static void main(String a[])
	{
		Scanner scanner = new Scanner(System.in);
		long start = System.currentTimeMillis();
		Test test = new Test();
		int noOfDivisors = 0;
		int input = scanner.nextInt();
		if(input == 1)
		{
			noOfDivisors = 1;
		}
		else
		{
			for(int j=1; j*j<=input; j++)
			{
				if(input%j == 0)
				{
					String s1 = Integer.toString(input);
					String s2= Integer.toString(j);
					
					if(test.present(s1, s2))
						++noOfDivisors;
					if(j>1)
					{
						String s3=Integer.toString(input/j);
						if(!s3.equals(s2))
							if(test.present(s1, s3))
								++noOfDivisors;
					}
				}
			}
			noOfDivisors++;
		}
		System.out.println(noOfDivisors);
		//System.out.println("Time in milli seconds: "+((System.currentTimeMillis()-start)));
		
	}
	
	boolean present(String s1, String s2)
	{
		char s3[] = s2.toCharArray();
		for(int i=0; i<s3.length; i++)
		{
			if(s1.contains(Character.toString(s3[i])))
			{
				return true;
			}
		}
		return false;
	}

}
