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
#include <bits/stdc++.h>
using namespace std;
int main() {
  int i, j;
  int x, n = 0, temp1, temp2;
  string str1;
  char str[15], str2[15], str3[15];
  cin >> x;
  if (x == 1) {
    cout << 1 << endl;
    return 0;
  }
  sprintf(str, "%d", x);
  str1.assign(str);
  for (i = 1; i * i <= x; i++) {
    if (x % i == 0) {
      for (j = 0; j < 15; j++) str2[j] = str3[j] = '\0';
      sprintf(str2, "%d", i);
      sprintf(str3, "%d", x / i);
      temp1 = strlen(str2);
      temp2 = strlen(str3);
      for (j = 0; j < temp1; j++) {
        if (str1.find(str2[j], 0) < str1.length()) {
          n++;
          break;
        }
      }
      if (i != (x / i))
        for (j = 0; j < temp2; j++) {
          if (str1.find(str3[j], 0) < str1.length()) {
            n++;
            break;
          }
        }
    }
  }
  cout << n << endl;
  return 0;
}
