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 start():
    x = input()
    answer = 0
    y = str(x)
    for i in xrange(1,x+1):
        if i*i > x: break
        if x%i == 0:
            answer += int(True in map(y.__contains__, list(str(i))))
            if i != x/i:
                answer += int(True in map(y.__contains__, list(str(x/i))))
    print answer

start()
