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

public class B136{      
        
        private BufferedReader in;  
        private StringTokenizer st;
        private PrintWriter out;
        boolean []e;
        
        boolean test(int a){
            
            while(a != 0){
                if(e[a%10]) return true;
                a/=10;
            }
            return false;
        }
        void solve() throws IOException{

            e = new boolean[10];
            int x = nextInt();
            int y = x;
            while(y!=0){
                e[y%10] = true;
                y/= 10;
            }
            int ans = 0;
            for (int i = 1; (long)i*i <= x; i++) {
                if(x%i == 0){
                    if(test(i)) ans++;
                    if(x/i != i && test(x/i)) ans++;
                }
            }
            out.println(ans);
        }
            

        B136() throws IOException {
            in = new BufferedReader(new InputStreamReader(System.in));      
            out = new PrintWriter(System.out);
            eat("");
            solve();            
            out.close();            
        }

        private void eat(String str) {
            st = new StringTokenizer(str);
        }

        String next() throws IOException {
            while (!st.hasMoreTokens()) {
                String line = in.readLine();
                if (line == null) {
                    return null;
                }
                eat(line);
            }
            return st.nextToken();
        }

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

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

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

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

        int gcd(int a,int b){
            if(b>a) return gcd(b,a);
            if(b==0) return a;
            return gcd(b,a%b);
        }

}
