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.io.*;
import java.util.*;
public class C136B
{

    /**
     * @param args
     */
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int sqrt = (int)Math.sqrt(n);
        HashSet<Integer> fac = new HashSet<Integer>();
        fac.add(1);
        fac.add(n);
        for (int i = 2; i <= sqrt; i++)
        {
            if (n % i == 0)
            {
                fac.add(i);
                fac.add(n / i);
            }
        }
        int count = 0;
        for (Integer div : fac)
        {
            if (sharesDigit(n, div))
            {
                count++;
            }
        }
        System.out.println(count);
    }
    
    public static boolean sharesDigit (int x, int y)
    {
        int[] a = new int[10];
        while (x > 0) 
        {
            a[x % 10]++;
            x /= 10;
        }
        while (y > 0)
        {
            int b = y % 10;
            if (a[b] > 0) return true;
            y /= 10;
        }
        return false;
    }
}
