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

l1 = input()
#l2 = input().split()

#l1 = [int(i) for i in l1]
#l2 = [int(i) for i in l2]

n = int(l1)
m = list(l1)

div = []
total = 0

for k in range (1, int(math.sqrt(n))+1):
  if(n % k == 0):
    div.append(k); 
    if(n/k > k): div.append(int(n/k))


for i in div:
  cont = False
  lk = list(str(i))
  for j in lk:
    if j in m:
      cont = True
  if cont == True:
    total += 1

print(total)

   	 	 									 	 	     	   	