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 divisores(x):
    d = []
    if x == 1:
        return [1]
    i = 1
    while i*i <= x:
        if x%i == 0:
            d.append(i)
            if (i != x//i):
                d.append(x//i)
        i += 1
    return sorted(d)

def quebraDigitos(a):
    a = list(str(a))
    a = set(a)
    a = list(a)
    a = map(int, a)
    a = list(a)
    return a

def digitosEmComum(a,b):
    for c in a:
        if c in b:
            return True
    return False


x = int(input())
#qtd de divisores positivos d
#que tenham pelo menos 1 dígito comum

d = divisores(x)

#print(d)

dx = quebraDigitos(x)
cont = 0
for y in d:
    dd = quebraDigitos(y)
    z = digitosEmComum(dd,dx)
    if z:
        cont += 1

print(cont)
