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 *
s = set()
n = int(raw_input())
d = 1
sq = ceil(sqrt(n))
while d <= sq:
    if n % d == 0:
        s.add(d); s.add(n / d)
    d += 1
n_st = str(n)
cnt = 0
for e in s:
    st = str(e)
    for c in st:
        if c in n_st:
            cnt += 1
            break
print cnt