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

ds = raw_input()
d = int(ds)

def numb(a):
	a = '%s'%a
	for i in a:
		if i in ds:
			return True
	return False

s=0
for i in range(1,int(d**0.5)+1):
	if d % i ==0:
		s += int(numb(i)) + int(numb(d/i))
if int(d**0.5)**2 == d:
	s-= int(numb(int(d**0.5)))

print s
