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
t=1
for p in range(t):
    n=int(input())
    l=list(str(n))
    n=int(n)
    ans=0
    for i in range(1,int(math.sqrt(n)+1),1):
        if (n%i==0):
            num1=i
            f=0
            while(num1!=0):
                if (str(num1%10) in l):
                    f=1
                    break
                else:
                    num1=int(num1)
                    num1=num1//10
            if (f):
                ans+=1
            num2=n//i
            if ((n//i)!=i):
                f2=0
                while(num2!=0):
                    if (str(num2%10) in l):
                        f2=1
                        break
                    else:
                        num2=int(num2)
                        num2=num2//10
                if (f2):
                    ans+=1
    print(ans)