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.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Scanner;

/*************************************************************************
 *  Compilation:  javac TestAlgs4.java
 *  Execution:    java TestAlgs4 
 *  Dependencies: StdDraw.java
 *                http://introcs.cs.princeton.edu/mac/cover.jpg
 *  
 *  Draws a blue bullseye and textbook graphic.
 * 
 *************************************************************************/
public class Sourcecode {
    public static void main (String[] args) {
        
       Scanner scan=new Scanner(System.in);
       int source=scan.nextInt();
       int result=findanswer(source);
       System.out.println(result);
    }

    private static int findanswer(int source) {
        int count=0;
        for(int i=1;i<=Math.sqrt(source);i++){
            if(source%i!=0) continue;
            else{
                int half=source/i;
            if(commondigit(i,source)){
                count++;
            }
            if(half!=i&&commondigit(half,source)){
                count++;
            }
            }
        }
        return count;
    }

    private static boolean commondigit(int i, int source) {
        char[] chari = String.valueOf(i).toCharArray();
        String sourcestring=String.valueOf(source);
        for(int t=0;t<chari.length;t++){
            String achar=String.valueOf(chari[t]);
        int index=sourcestring.indexOf(achar);
        if(index!=-1){ return true;}
        }
        return false;
    }
    
}