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
x = int(input())
c = 0
ls_1 = []
for h in str(x):
    ls_1.append(h)
ls_x = set(ls_1)
for i in range(1,int(x**0.5)+1):
    if x % i == 0:
       ls_a = []
       for u in str(i):
           ls_a.append(u)
       ls_a = set(ls_a)
       if ls_x & ls_a != set():
           c += 1
       if x // i != i:
           ls_b = []
           for k in str(x//i):
               ls_b.append(k)
           ls_b = set(ls_b)
           if ls_x & ls_b != set():
               c+=1
print(c)