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
def isok(i , n):
    d = {}
    while i > 0:
        num = i % 10
        if d.get(num) == None:
            d[num] = 1
        else:
            d[num] += 1
        i /= 10
    while n > 0:
        num = n % 10
        if d.get(num) == None:
            n /= 10
        else:
            return True
    return False

n = int(raw_input())
i = 1
tot = 0
while i * i <= n:
    if n % i == 0 and isok(i , n) == True:
        tot += 1
    if n % (n / i) == 0 and i * i != n and isok(n / i , n) == True:
        tot += 1
    i += 1    

print tot
