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 math
n=long(raw_input());
st=str(n);
ctr=0;
for i in range(1,long(math.sqrt(n))+1):
	d=n%i;
	flag=0;flag1=0;
	if d==0:
		s=str(n/i);
		s1=str(i);
		#print s+" "+s1;
		if(s!=s1):
			for j in range(len(s)):
				if s[j] in st and flag==0:
					flag=1;
					ctr=ctr+1;
			for j1 in range(len(s1)):
				if s1[j1] in st and flag1==0:
					flag1=1;
					ctr=ctr+1;
		else:
			for j1 in range(len(s1)):
				if s1[j1] in st and flag1==0:
					flag1=1;
					ctr=ctr+1;
			
print ctr;
