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.*;
import java.io.*;

public class Main{

  BufferedReader in;
  StringTokenizer str = null;

  private String next() throws Exception{
    if(str == null || !str.hasMoreElements())
      str = new StringTokenizer(in.readLine());
    return str.nextToken();
  }

  private int nextInt() throws Exception{
    return Integer.parseInt(next());
  }

  public void run() throws Exception{
    in = new BufferedReader(new InputStreamReader(System.in)); 
    String s = next();
    long x = Long.parseLong(s);
    int ret = 0;

    for(long i=1;i*i<=x;i++){
      if (x % i == 0){
        if (check(s, i)) ret++;
        if (i != x/i && check(s, x/i)) ret++;
      }
    }
    System.out.println(ret);
  }

  private boolean check(String s, long i){
    String k = Long.toString(i);
    for(int j=0;j<k.length();j++)
      if (s.indexOf(k.charAt(j)) != -1)
        return true;
    return false;
  }

  public static void main(String args[]) throws Exception{
    new Main().run();  
  }
}