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
from sys import stdin ,stdout
from os import path
rd = lambda:stdin.readline().strip()
wr = stdout.write
if(path.exists('input.txt')):
    stdin = open("input.txt","r")
import time 
#------------------------------------
n = int(rd())
i = 1 
def compare(x,y):
	flag = False
	for i in x :
		if i in y :
			flag = True
			break
	return flag == True
if n == 1 :
	print(1)
else:	
	counter = 0 
	while i * i <= n:
		if n % i ==0 :
			result = compare(str(i),str(n))
			result2 = compare(str(n//i),str(n))
			if (n//i) == i:
				result = False
			counter+=(result2+result)
		i+=1
	print(counter)
