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
'''input
10
'''
def factor(n):
	return list(set(sum([[x, n//x] for x in range(1, int(n**0.5)+1) if n % x == 0], [])))
def same(a, b):
	if any(d in str(a) and d in str(b) for d in "0123456789"):
		return True
	return False
n = int(input())
t = 0
for x in factor(n):
	if same(x, n):
		t += 1
print(t)