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
n=int(input())
if n==1:
    print(1)
    exit()
count=0
import math as m
for x in range(1,int(m.sqrt(n))+1):
    ans=int(n)%int(x)
    num=str(n)
    nn=str(x)
    yy=str(n//x)
    for x in nn:
        if x in num and ans==0:
            #print(nn)
            count+=1
            break
    for x in yy:
        if x in num and ans==0 and yy!=nn:
            #print(yy)
            count+=1
            break
if count==0:
    count+=1

print(count)