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
wyst = [0] * 10

def sprawdz(divi):
    while (divi > 0):
        divi, r = divmod(divi,10)
        if wyst[r] :
            return 1
    return 0

def zapelnij(x):
    while x > 0:
        x, r = divmod(x,10)
        wyst[r] = 1

def policz(x):
    i = 1
    wynik = 0
    while i*i < x:
        if x % i == 0:
            if sprawdz(i):
                wynik += 1
            if sprawdz(x/i):
                wynik += 1
        i += 1
    if (i*i == x):
        if sprawdz(i):
            wynik += 1;
    return wynik

def main():
    N = int(raw_input())
    zapelnij(N)
    print policz(N)

main()
