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

def check(s1,s2):
	for i in range(len(s1)):
		for j in range(len(s2)):
			if(s1[i]==s2[j]):
				return True
	return False

N = int(input())
div = 0
bound = math.floor(math.sqrt(N))
for i in range(bound):
	k = i+1
	if(N%k==0):
		f1 = str(k)
		f2 = str(N//k)
		if(check(f1,str(N))):
			div += 1
		if(f1!=f2 and check(f2,str(N))):
			div += 1
print (div)
		