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.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	private BufferedReader br;
	private StringTokenizer tokenizer;
	private PrintWriter pw;
	
	private int n = 0;
	String t = "";
	boolean chrs[] = new boolean[2567];
	
	private void solve() throws IOException {
		n = nextInt();
		
		t = String.valueOf(n);
		
		for (int i = 0; i < t.length(); ++i)
			chrs[t.charAt(i)] = true;
		
		int ans = 0;
		for (int i = 1; i <= (int)Math.sqrt(n); ++i) {
			if (n % i == 0) {
				ans += dig(i);
				ans += dig(n / i);
			}
		}
		
		if ((int)Math.sqrt(n) * (int)Math.sqrt(n) == n) {
			ans -= dig((int)Math.sqrt(n));
		}

		pw.print(ans);
	}
	
	private int dig(int i) {
		String s = String.valueOf(i);
		
		for (int z = 0; z < s.length(); ++z) {
			if (chrs[s.charAt(z)])
				return 1;
		}
		return 0;
	}
	
	public static void main(String[] args) {
		new Main().run();
	}

	public void run() {
		try {
			pw = new PrintWriter(System.out);
			br = new BufferedReader(new InputStreamReader(System.in));
			solve();
			pw.close();
			br.close();
		} catch (IOException e) {
			System.err.println("IO Error");
		}
	}

	int nextInt() throws IOException {
		return Integer.parseInt(nextToken());
	}

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

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

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

		return tokenizer.nextToken();
	}
}