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.Scanner;
public class LittleElephant {

 /**
  * @param args
  */
 public static void main(String[] args) {
   
      Scanner sc = new Scanner(System.in);
   int n = sc.nextInt();
   int limit = (int)Math.sqrt(n);
   
   int total = 0;
   
   for (int i = 1; i <= limit; i++) {
    if (n % i == 0) {
     if (check(n, i)) {
      //System.out.println(i);
      total++;
     }
     int j = n / i;
     if (i != j) {
      if (check(n, j)) {
       //System.out.println(ninja);
       total++;
      }
     }
    }
   }
   System.out.println(total);   
  }

public static boolean check(int source, int test) {
 String a = String.valueOf(source);
 String b = String.valueOf(test);
 boolean hasCommonCharacter = false;
 
 for (int i = 0; i < a.length(); i++) {
  if (b.contains(String.valueOf(a.charAt(i)))) {
   hasCommonCharacter = true;
   break;
  }
 }
 
 return hasCommonCharacter;
}
}