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 sys

w = sys.stdout.write
read = sys.stdin.readline
reads = sys.stdin.read

def r(f=None):
    if f:
        return map(f, read().split())
    else:
        return read().split()

def rs(t,f=None):
    result = []
    result_append = result.append
    for i in xrange(t):
        if f:
            result_append(tuple(map(f, read().split())))
        else:
            result_append(list(read()))
    return result


####################################################
import math
sqrt = math.sqrt
from collections import deque


[x] = r(int)
nums = set(list(str(x)))

def next(s, n, k):
    l = s.rfind('1')
    if l < n-1:
       return "%s01%s" % (s[:l], "0"*(n-l-2))
    else:
        ss = s.rstrip('1')
        nn = len(ss)
        l = ss.rfind('1')
        if l < 0:
            return None
        return "%s01%s%s" % (ss[:l], "1"*(n-nn), "0"*(nn-l-2))

k = 0
for i in xrange(1, int(sqrt(x))+1, 1):
    if x/i*i == x:
        s = set(str(i))
        if len(s-nums) < len(s):
            k += 1
        if i != x/i:
            s = set(str(x/i))
            if len(s-nums) < len(s):
                k += 1
w(str(k))
    
    
    
    