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=int(input())
flag=0
for i in range(1,int(math.sqrt(a))+1):
    if(a%i==0):
        if(a/i==i):
            p=str(int(i))
            for j in range(0,len(p)):
                if(p[j] in str(a)):
                    flag=flag+1
                    break
        else:
            p=str(int(i))
            for j in range(len(p)):
                if(p[j] in str(a)):
                    flag=flag+1
                    break
            b=str(int(a/i))
            for j in range(len(b)):
                if b[j] in str(a):
                    flag=flag+1
                    break
print(flag)