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 math import *

def is_good(a, b):
    A = set()
    B = set()
    while a > 0:
        A.add(a % 10)
        a /= 10
    while b > 0:
        B.add(b % 10)
        b /= 10
    if len(A & B) > 0:
        return True
    else:
        return False

x = int(raw_input())
ans = 0
for d in range(1, int(sqrt(x) + 1)):
    if x % d == 0:
        if is_good(x, d):
            ans += 1
        if d * d != x:
            if is_good(x, x / d):
                ans += 1
print ans