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
def is_match(n):
  while n!= 0:
    if digit[n % 10]:
      return True
    n = int(n / 10)
  return False

x = int(input())
x2 = x
digit = list()
d = 1
count = 0

for i in range(10):
  digit.append(False)

while x2 != 0:
  digit[x2 % 10] = True
  x2 = int(x2 / 10)

while d * d < x:
  if x% d == 0:
    if(is_match(d)):
      count += 1
    if(is_match(int(x / d))):
      count += 1
  d += 1

if d * d == x and is_match(d):
  count += 1

print(count)




 			 			    	 	 	  			   	 	 		