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

public class Main{

    boolean debug=false;

    void solve(){
	Scanner sc=new Scanner(System.in);
	int x=sc.nextInt();
	boolean[] flag=new boolean[10];
	int a=x;
	while(a>0){
	    flag[a%10]=true;
	    a/=10;
	}
	if(debug)System.out.println("debug");

	int count=0;
	for(int i=1;i<=Math.sqrt(x);i++){
	    if(x%i==0){
	       
		int d1=x/i;
		int d2=x/d1;
	    

		int a1=d1;int a2=d2;
		if(debug)System.out.printf("a1=%d a2=%d\n",a1,a2);
		boolean f1=false;boolean f2=false;
		while(a1>0){
		    if(flag[a1%10])f1=true;
		    a1/=10;
		}
		while(a2>0){
		    if(flag[a2%10])f2=true;
		    a2/=10;
		}
	      
		if(f1){count++;}
		if(d1!=d2 && f2){count++;}
	    }
	}

	System.out.println(count);
    }
    public static void main(String[] args){
	new Main().solve();
    }
}

