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 = int(raw_input())

digitnum = [0]*10
for i in (int(x) for x in list(str(n))):
    digitnum[i] += 1;

def check(v):
    for i in (int(x) for x in list(str(v))):
        if digitnum[i] != 0:
            return True
    return False

len = int(math.sqrt(n) + 1)
ret = 0
for i in xrange(1,len):
    if n%i == 0:
       if check(i):
           ret += 1
       if n/i != i:
           if check(n/i):
               ret += 1
print ret 