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 B {
    public static void main(String[] args) throws Exception {
        new B().solve();
    }
    
    boolean[] xd=new boolean[10];//0~9
    void solve() throws IOException {
        // BufferedReader in = new BufferedReader(new
        // InputStreamReader(System.in));
        Scanner sc = new Scanner(System.in);
        int x=sc.nextInt();
        
        for(int xx=x; xx>0; xx/=10){
            xd[xx%10]=true;
        }
        
        int count=0;
        for(int k=1; k*k<=x; k++){
            if(x%k==0){
                //k, x/k
                if(check(k)){
                    count++;
                }
                if(k*k<x && check(x/k)){
                    count++;
                }
            }
        }      
        System.out.println(count);
          
    }
    
    boolean check(int k){
        for(int kk=k; kk>0; kk/=10){
            if(xd[kk%10]){
                return true;
            }
        }
        return false;
    }
}

