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 java.util.Scanner;

public class B
{
    static boolean sameDigits(int one, int two)
    {
        int[] digitsOne = new int[10];
        int[] digitsTwo = new int[10];

        do
        {
            digitsOne[one % 10]++;
            one -= one % 10;
            one /= 10;
        }while (one != 0);

        do
        {
            digitsTwo[two % 10]++;
            two -= two % 10;
            two /= 10;
        }while (two != 0);

        for(int i = 0; i < 10; i++)
            if((digitsOne[i] > 0) && (digitsTwo[i] > 0))
                return true;
        return false;
    }

    public static void main(String args[])
    {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int count = 0;

        for(int i = 1; i < (int)Math.sqrt(N) + 1; i++)
        {
            if(N % i == 0)
            {
                if(sameDigits(i, N))
                    count++;
                if((N / i != i) && sameDigits(N / i, N))
                    count++;
            }
        }
        System.out.println(count);
    }
}
