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
from math import floor, sqrt, ceil
n = int(input())
digits = set()
x = n
while(x > 0):
    digits.add(x % 10)
    x //= 10

if(n <= 9):
    print("1")
else:
    result = set()
    for i in range(1, ceil(sqrt(n)) + 1):
        x, y = i, n // i
        if(n % x == 0):
            while(x > 0):
                if(x % 10 in digits):
                    result.add(i)
                    break
                x //= 10
        if(n % y == 0):
            while(y > 0):
                if(y % 10 in digits):
                    result.add(n // i)
                    break
                y //= 10
    
    print(len(result))