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
n=int(input())

def single(n):
    l=[]
    while n!=0:
       a=n%10
       l.append(a)
       n=n//10
    
    return l   

def simple(n):
  l=[]
  x=int(math.sqrt(n))
  for i in range(1,x+1):
      if n%i==0:
         if i*i==n:
            l.append(i)
         else:
            l.append(i)
            l.append(n//i)
   
  return l          

temp=simple(n)
count=0
mlist=single(n)
for i in range(len(temp)):
    pink=single(temp[i])
    done=0
    for j in pink:
        if j in mlist:
           done=1
    
    if done==1:
       count+=1
    
print(count)       



