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
#coding:utf-8

import math

x = int(raw_input())
a = list(0 for i in range(10))
s=list()
m = x
while x:
	a[x % 10] += 1
	x /= 10
ans = 0
for i in range(1, int(math.sqrt(m)) + 1):
	if m % i == 0:
		j = i
		while j:
			if a[j % 10]:
				ans += 1
				break
			j /= 10
		j = m / i
		if i * i != m:
			while j:
				if a[j % 10]:
					ans += 1
					break
				j /= 10
print(ans)