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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {

		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		
		int x = sc.nextInt();
		int c = 0;
		for(int i = 1; i * i <= x; ++i)
			if(x%i == 0)
			{
				if(match(x, i))
					++c;
				if((x/i) != i && match(x, x/i))
				++c;
			}
		out.println(c);
		out.flush();
		out.close();
	}
	
	static boolean match(int x, int y)
	{
		boolean[] c = new boolean[10];
		while(x > 0)
		{
			c[x%10] = true;
			x /= 10;
		}
		while(y > 0)
			if(c[y%10])
				return true;
			else
				y /= 10;
		return false;
	}

	static class Scanner 
	{
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s){	br = new BufferedReader(new InputStreamReader(s));}

		public String next() throws IOException 
		{
			while (st == null || !st.hasMoreTokens()) 
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {return Integer.parseInt(next());}
		
		public long nextLong() throws IOException {return Long.parseLong(next());}
		
	}
}
