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.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {

    /**
     * @param args
     */
    
     private static final File _ = new File("input.in");
     
    public static void main(String[] args) throws IOException {
        // TODO Auto-generated method stub
        BufferedReader br = _.exists() ? new BufferedReader(new FileReader(_))
        : new BufferedReader(new InputStreamReader(System.in));


        String sx,si,si1;
        int x,d;
        while( (sx=br.readLine())!=null){
        x=Integer.parseInt(sx); d=0;
        for(int i=1; i*i <= x; i++){
            if(x%i==0){
            	si=i+"";
            	si1=(x/i)+"";
                for(int j =0; j <si.length(); j++){
                    if(sx.contains(si.charAt(j)+"")){
                    d++;
                    break;
                    }
                }
                if(!si.equals(si1))
                for(int j1 =0; j1 <si1.length(); j1++){
                    if(sx.contains(si1.charAt(j1)+"")){
                    d++;
                    break;
                    }
                }
            }
        }
        System.out.println(d);
        }
        
    }

}