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

public class B {

    static boolean[] isPrime;
    static int[] primes;
    static int index;

    public static void seive() {
        index = 0;
        isPrime = new boolean[1000000];
        primes = new int[1000000];
        for (int i = 2; i < isPrime.length; i++)
            if (!isPrime[i]) {
                primes[index++] = i;
                for (int j = i + i; j < isPrime.length; j += i)
                    isPrime[j] = true;
            }
    }

    public static void main(String[] args) {
        seive();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Integer> list = getDiv(n);
        int s = list.size();
        int count = 0;
        for (int i = 0; i < s; i++)
            if (can(list.get(i), n)) {

                count++;
            }
        System.out.println(count);
    }

    private static boolean can(int ii, int n) {
        String s1 = ii + "";
        String s2 = n + "";
        boolean[] num = new boolean[10];
        for (int i = 0; i < s1.length(); i++)
            num[s1.charAt(i) - '0'] = true;
        for (int i = 0; i < s2.length(); i++)
            if (num[s2.charAt(i) - '0'])
                return true;
        return false;
    }

    private static ArrayList<Integer> getDiv(int i) {
        int k = 0;
        int PF = primes[k++];
        int[] count = new int[1000000];
        while (i != 1 && PF * PF <= i) {
            int c = 0;
            while (i % PF == 0) {
                c++;
                i /= PF;
            }
            count[PF] = c;
            PF = primes[k++];
        }
        ArrayList<Integer> list = new ArrayList<Integer>();
        fill(list, count, 1, 2);
        if (i != 1)
            fill(list, count, i, 2);
        return list;
    }

    private static void fill(ArrayList<Integer> list, int[] count, int prev,
            int ind) {
        if (ind == index)
            list.add(prev);
        else {
            while (ind < index && count[ind] == 0)
                ind++;
            if (ind < index)
                for (int j = 0; j <= count[ind]; j++)
                    fill(list, count, (int) (prev * Math.pow(ind, j)), ind + 1);
            else
                list.add(prev);
        }

    }

}
