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 get_dec_nums(num):
    nums=set()
    while num>=10:
        nums.add(num%10)
        if len(nums)>9:
            break
        num//=10
    nums.add(num)
    return list(nums)


def one_overlap(nums,t):
    tnums=get_dec_nums(t)
    for c in nums:
        for d in tnums:
            if c==d:
                return 1
    return 0

n=int(input())
d=0
nums=get_dec_nums(n)
sq=int(floor(sqrt(n)))
for c in range(1,sq+1):
    if n%c==0:
        if(one_overlap(nums,c)):
            d+=1
        if(one_overlap(nums,n//c) and c!=n//c):
            d+=1
print(d)
