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
'''
Created on 2012-9-4

@author: gaoxun
'''
def cal(n,li):
    while(n > 0):
        if(li[n % 10]):
            return 1
        n /= 10
    return 0

n = input()
li = [0 for i in range(20)]
a = n
sums = 0
while a > 0:
    li[a % 10] = 1
    a /= 10

i = 1
while i*i <= n:
    if n % i ==0:
        sums += cal(i,li)
        if i * i != n:
            sums += cal(n/i,li)
    i += 1
print sums