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.*;
public class a
{
    public static void main(String[] args)
    {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        boolean[] digits = new boolean[10];
        for(int i = 0; i<(n+"").length(); i++)
            digits[(n+"").charAt(i) - '0'] = true;
        int res = 0;
        for(int i = 1; i<=Math.sqrt(n); i++)
        {
            if(n%i != 0) continue;
            for(int j = 0; j<(i+"").length(); j++)
                if(digits[(i+"").charAt(j) - '0'])
                {
                    res++;
                    break;
                }
            if(i == n/i)
                continue;
            for(int j = 0; j<(n/i+"").length(); j++)
                if(digits[(n/i+"").charAt(j) - '0'])
                {
                    res++;
                    break;
                }
        }
        System.out.println(res);
    }
}