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
import math
a = input()
if a == 1:
    print 1
else:   
    s = math.ceil(math.sqrt(a))
    l1 = []
    def n_to_list(n):
        a = str(n)
        l = []
        for r in range(len(a)):
            l.append(int(a[r]))
        return l
    def find_common_digits(a, b):
        return (len(list(set(n_to_list(a)) & set(n_to_list(b)))) != 0)
    s = int(s)
    for r in range(1, s+1):
        if (a%r) == 0:
            l1.append(r)
            if a/r != r:
                l1.append(a/r)
    l1 = list(set(l1))

    c = 0

    for e in l1:
        if find_common_digits(a, e):
            c += 1
    print c
