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.StringTokenizer;

public class Main {
	int ok(int num, int x) {
		boolean[] was = new boolean[15];
		while (num > 0) {
			was[num % 10] = true;
			num /= 10;
		}
		while (x > 0) {
			if (was[x % 10])
				return 1;
			x /= 10;
		}
		return 0;
	}

	void solve() throws IOException {
		int x = nextInt();
		int ans = 0;
		for (int i = 1; i * i <= x; ++i)
			if (x % i == 0) {
				ans += ok(i, x);
				if (x / i != i)
					ans += ok(x / i, x);
			}
		writer.println(ans);
	}

	BufferedReader reader;
	PrintWriter writer;
	StringTokenizer tokenizer;

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

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

	public void run() {
		try {
			reader = new BufferedReader(new InputStreamReader(System.in));
			tokenizer = null;
			writer = new PrintWriter(System.out);
			solve();
			reader.close();
			writer.close();
		} catch (Exception e) {
			e.printStackTrace();
			System.exit(1);
		}
	}

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