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 sys,math
'''
def opt(weight,value,n,w):
    f=[0]*(n+1)
    for i in range(n+1):
        f[i] = max(v[i]


n,w = map(int,input().split())
weight=[]
value=[]
for _ in range(n):
    W,V = map(int,input().split())
    weight.append(W)
    value.append(N)
print(opt(weight,value,n,w))
'''
def ret(n,i):
    i=str(i)
    n=str(n)
    for x in i:
        if x in n:
            return True
    return False

n = int(input())
c=0
for i in range(1,int(n**0.5)+1):
    if n%i == 0:
        if n//i == i:
            if ret(n,i):
                c+=1
                continue
        if ret(n,i):
            c+=1
        if ret(n,n//i):
            c+=1
print(c)
