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 -*- 
#===========================================================================// 
# Author: Zakhar_Voit
# Module: main
# Description: 
# Creation date: 31.08.2012 18:28:18
# Remarks: 
#===========================================================================//

try:
    read = raw_input
except:
    read = input

readints = lambda: map(int, read().split())

x, = readints()
sx = str(x)

def check(a):
    a = str(a)
    for q in a:
        for w in sx:
            if q == w:
                return True
    return False

cur = 1
ans = 0
div = []
while cur * cur <= x:
    if x % cur == 0:
        div.append(cur)
        if x / cur != cur:
        	div.append(x / cur)
    cur += 1

for cur in div:
    if check(cur):
        ans += 1

print ans
