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 final class little_elephant_and_num
{
    static FastScanner sc=new FastScanner(new BufferedReader(new InputStreamReader(System.in)));
    static PrintWriter out=new PrintWriter(System.out);
	
    public static void main(String args[]) throws Exception
    {
		long x=sc.nextLong();
		char[] a=Long.toString(x).toCharArray();
		boolean[] v=new boolean[10];
		List<Long> list=new ArrayList<Long>();
		for(char ch:a)
		{
			int curr=Integer.parseInt(ch+"");
			v[curr]=true;
		}
		long i;
		for(i=1;(i*i)<x;i++)
		{
			if(x%i==0)
			{
				list.add(i);
				list.add(x/i);
			}
		}
		if(i*i==x)
		{
			list.add(i);
		}
		int c=0;
		for(long l:list)
		{
			boolean curr=false;
			char[] b=Long.toString(l).toCharArray();
			for(char ch:b)
			{
				int num=Integer.parseInt(ch+"");
				if(v[num])
				{
					curr=true;
					break;
				}
			}
			if(curr)
			{
				c++;
			}
		}
		out.println(c);
		out.close();
    }
}
class FastScanner
{
    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }
	
    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }
	
	public String next() throws Exception {
		return nextToken().toString();
	}
	
    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }
}