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 B {

    private static HashMap<Integer, Boolean> map;
    private static TreeSet<Integer> divisors;
    private static int m;

    public static void rec2(int n, ArrayList<Integer> pfactors) {
	if(n <= 9) {	    
	    return;
	} else {
	    for(int i=0; i<pfactors.size(); ++ i) {
		int p = pfactors.get(i);
		if(m % p == 0) {
		    divisors.add(m / p);
		    rec(m / p, pfactors);
		}
	    }
	}
    }

    public static void rec(int n, ArrayList<Integer> pfactors) {
	if(map.containsKey(n)) return;
	map.put(n, true);
	for(int i = 0; i < pfactors.size(); ++ i) {
	    int p = n * pfactors.get(i);
	    if(m % p == 0) {
		divisors.add(p);		
		rec(p, pfactors);
	    }
	} 
    }
    
    public static ArrayList<Integer> getPrimes(int n) {
	boolean[] prime = new boolean[n + 1];
	Arrays.fill(prime, true);
	ArrayList<Integer> res = new ArrayList<Integer>();
	prime[0] = false;
	prime[1] = false;
	int m = (int) Math.sqrt(n);
	for(int i = 2; i <= m; ++i) {
	    if(prime[i]) {		
		for(int k = i*i; k <= n; k += i) {
		    prime[k] = false;
		}
	    }
	}
	for(int i=0; i<=n; ++i) if(prime[i]) res.add(i);
	return res;
    }

    public static ArrayList<Integer> getPrimeFactors(int n, ArrayList<Integer> primes) {
	ArrayList<Integer> res = new ArrayList<Integer>();
	int k = 0;
	while(n > 0) {
	    if(n % primes.get(k) == 0) {
		res.add(primes.get(k));
		n /= primes.get(k);		
	    } else {		
		++ k;
	    }
	    if(k >= primes.size()) break;
	}
	return res;
    } 

    public static int count(TreeSet<Integer> divs, int n) {
	String r = String.valueOf(n);
	int c = 0;
	for(int p : divs) {
	    while(p > 0) {
		String q = String.valueOf(p % 10);
		p /= 10;
		if(r.indexOf(q) >= 0) {
		    ++ c;
		    break;
		}		
	    }
	}
	return c;
    }

    public static int dummy(int n) {
	TreeSet<Integer> set = new TreeSet<Integer>();
	for(int i=1; i<= n; ++i) {
	    if(n % i == 0) {
		//System.out.println("Dummy divisor => " + i);
		set.add(i);
	    }
	}
	return count(set, n);
    }

    public static void main(String[] args) {
	
	Scanner in = new Scanner(System.in);

	m = in.nextInt();

	map = new HashMap<Integer, Boolean>();
	divisors = new TreeSet<Integer>();
        TreeSet<Integer> factors = new TreeSet<Integer>();

	ArrayList<Integer> primes = getPrimes(10000000);
	ArrayList<Integer> primeFactors = getPrimeFactors(m, primes);
	ArrayList<Integer> inter = new ArrayList<Integer>();
	for(int i = 0; i < primeFactors.size(); ++i)
	    for(int j = i + 1; j < primeFactors.size(); ++ j)
		inter.add(primeFactors.get(i) * primeFactors.get(j));

	//for(int pr : primes)
	    
	
	factors.addAll(primeFactors);
	factors.addAll(inter);
	//System.out.println("Fac primes => " + primeFactors);
	ArrayList<Integer> list = new ArrayList<Integer>();
	for(int n : factors)
	    list.add(n);
	for(int n : list)
	    rec(n, list);

	rec2(m, list);

	divisors.add(1);
	divisors.add(m);
	divisors.addAll(factors);
	//System.out.println("Bef " + divisors);		
	ArrayList<Integer> list2 = new ArrayList<Integer>();
	for(int p : divisors) list2.add(p);
	rec2(m, list2);
	//	System.out.println("Aft " + primes.get(primes.size() - 1));		
	System.out.println(count(divisors, m)/* + " = " + dummy(m)*/);
	//	System.out.println(dummy(m));

    }

}