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 sqrt

number = int(input())
num = number

def is_at_array_div(divisor, array_div, array_div_population):
    for div_idx in range(len(array_div)):
        if divisor == array_div[div_idx]:
            array_div_population[div_idx] += 1
            return
    array_div_population.append(1)
    array_div.append(divisor)


def get_divisors(array_div, array_div_population):
    divisors = [1]

    for div_idx in range(len(array_div)):

        divisors = multiply_fact_n_times(divisors, array_div[div_idx], array_div_population[div_idx])
    return divisors


def multiply_fact_n_times(divisors, factor, n_times):
    new_divisors = []
    for div in divisors:
        result = div * factor
        new_divisors.append(result)
    divisors = divisors + new_divisors

    while n_times-1 > 0:
        final_divisors = []
        for div in new_divisors:
            result = div * factor
            final_divisors.append(result)
        divisors = divisors + final_divisors
        new_divisors = final_divisors
        n_times -= 1
    return divisors


array_div = []
array_div_population = []
factor_count = 2
plus_two = False
max_size = sqrt(num)
# get_factors(num)
while num != 1:
    if num % factor_count == 0:
        num //= factor_count
        is_at_array_div(factor_count, array_div, array_div_population)

    else:
        if not plus_two:
            factor_count += 1
            plus_two = True
        else:
            factor_count += 2

        if factor_count > max_size:
            factor_count = num

divisors = list(sorted(get_divisors(array_div, array_div_population)))


def has_equal_digits(number, divisor):
    number = str(number)
    divisor = str(divisor)

    for num_digit in number:
        for div_digit in divisor:
            if num_digit == div_digit:
                return True
    return False

count = 0
for divisor in divisors:
    if has_equal_digits(number, divisor):
        count += 1
print(count)
 	 		     		  	  	   		   		 		