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
lis=[]
def check(n):
    while n!=0:
        for i in range(len(lis)):
            if(n%10==lis[i]):
                return True
        n=int(n/10)
    else :
        return False;
def main():
    n=int(input())
    a=n
    m=n**0.5+0.5
    while n!=0:
        global lis
        lis.append(n%10)
        n=int(n/10)
    jishu=0
    i=1
    while i<=m:
        if(a%i==0):
            if(check(i)):
                jishu+=1
            if(a/i!=i and check(int(a/i))):
                jishu+=1
        i+=1
    print(jishu)
main()


   	 	   	  			  	    						 		