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.awt.Point;
import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.math.BigInteger;
import java.io.*;
import java.util.*;

public class Main {

    private int[] dig = new int[10];

    public void solve()throws Exception {
        int N = nextInt();
        Vector<Integer> V = new Vector<Integer>();

        int num = N;
        while (num > 0) {
            dig[num%10]++;
            num /= 10;
        }

        int end = (int) Math.sqrt((double) N) + 1;
        for (int i = 1; i < end; ++i) {
            if (N%i == 0)
                V.add(i);
            if (N%(N/i) == 0 && (N/i) != i)
                V.add(N/i);
        }
        int ans = 0;
        for (Integer i : V)
            if (same(i))
                ans++;

        writer.println(ans);
    }

    private boolean same(int num) {
        while (num > 0) {
            if (dig[num%10] > 0)
                return true;
            num /= 10;
        }
        return false;
    }

    /*
    ***********************************************************************
    */
    PrintWriter writer;
    BufferedReader reader;

    StringTokenizer stk;

    void run()throws Exception {
        stk = null;
        reader = new BufferedReader(new InputStreamReader(System.in));
        writer = new PrintWriter(System.out);
        solve();
        reader.close();
        writer.close();
    }
    int nextInt()throws Exception {
        return Integer.parseInt(nextToken());
    }
    long nextLong()throws Exception {
        return Long.parseLong(nextToken());
    }
    double nextDouble()throws Exception {
        return Double.parseDouble(nextToken());
    }
    String nextString()throws Exception {
        return nextToken();
    }
    String nextLine()throws Exception {
        return reader.readLine();
    }
    String nextToken()throws Exception {
        if(stk == null || !stk.hasMoreTokens()) {
            stk = new StringTokenizer(nextLine());
            return nextToken();
        }
        return stk.nextToken();
    }
    public class Pair<T, U> implements Comparable<Pair<T, U>> {
        T x;
        U y;
        public Pair (){}
        public Pair (T x, U y) {
            this.x = x;
            this.y = y;
        }
        public Pair<T, U> makePair(T x, U y) {
            this.x = x;
            this.y = y;
            return this;
        }
        @Override
        public int compareTo(Pair<T, U> o) {
            int cmp = compare(this.x, o.x);
            return (cmp == 0) ? compare(this.y, o.y) : cmp;
        }
        private int compare(Object o1, Object o2) {
            return (o1 == null) ? (o2 == null) ? 0 : -1 : (o2 == null) ? +1 : ((Comparable) o1).compareTo(o2);
        }
        @Override
        public String toString() {
            return this.x.toString() + " " + this.y.toString();
        }
    };
    public static void main(String[]args) throws Exception {
        new Main().run();
    }
}