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 LittleElephantAndNumbers{
    BufferedReader in;
    PrintWriter out;
    StringTokenizer st;

    String strX;
    public void run() throws Exception {
        //in = new BufferedReader(new FileReader("D.IN"));
        in = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);

        int x=nextInt();
        strX=x+"";
        int ret=0;
        for (int d = 1; d*d <= x; d++) {
			if(x%d==0)
			{
				if( canExpress(d)) {ret++;}
				if(x==d*d) continue;
				if(canExpress(x/d)) {ret++;}
			}
		}
        System.out.println(ret);

        out.flush();
        out.close();
        in.close();
    }
    public boolean canExpress(int d)
    {
    	while(d>0)
    	{
    		int num= d%10;
    		if(strX.indexOf((char)(num+'0'))>=0) return true;
    		d/=10;
    	}
    	return false;
    }

    public static void main(String[] args) throws Exception {
        new LittleElephantAndNumbers().run();
    }

    String next() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(in.readLine());
            } catch (Exception e) {
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }
}
