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.*;
import static java.lang.Math.*;
public class ProblemB {
    void run() {
		int x = nextInt();
		int dx = digits(x);
		int count = 0;
		for (int d = 1; d*d <= x; ++d) {
			if (x % d == 0) {
				int dd = digits(d);
				if ((dd & dx) > 0) {
					++count;
					d(d);
				}
				int e = x / d;
				if (e != d) {
					int de = digits(e);
					if ((de & dx) > 0) {
						++count;
						d(e);
					}
				}
			}
		}
		p("%d\n", count);
    }

	int digits(int x) {
		int ret = 0;
		while (x > 0) {
			ret = ret | (1 << (x % 10));
			x /= 10;
		}
		return ret; // nothing to see here
	}

    boolean debug = false;
    void p(String f, Object...params) {
        System.out.printf(f, params);
    }
    void d(Object...params) {
        if (debug) {
            p("DEBUG: %s\n", Arrays.deepToString(params));
        }
    }
    void die() {
        throw new RuntimeException();
    }
    public ProblemB(String[] args) {
        if (args.length > 0 && args[0].equals("debug")) {
            debug = true;
        }
        in = new BufferedReader(new InputStreamReader(System.in));
    }
    public static void main(String[] args) {
        new ProblemB(args).run();
    }

    BufferedReader in;
    StringTokenizer tok;
    void tokenizeLine() {
        try {
            String line = in.readLine();
            if (line == null) die();
            tok = new StringTokenizer(line);
        } catch (IOException e) {
            die();
        }
    }
    String next() {
        while (tok == null || !tok.hasMoreTokens()) {
            tokenizeLine();
        }
        return tok.nextToken();
    }
    String nextLine() {
        if (tok == null) {
            tokenizeLine();
        }
        String ret = tok.hasMoreTokens() ? tok.nextToken("\n"): "";
        tok = null;
        return ret;
    }
    int nextInt() {
        return Integer.parseInt(next());
    }
    long nextLong() {
        return Long.parseLong(next());
    }
    double nextDouble() {
        return Double.parseDouble(next());
    }
}
