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;
vector<int> v;
int flag[10] = {};
int iscon(int num) {
  int i, k, m;
  char stmp[1000];
  sprintf(stmp, "%d", num);
  for (k = 0; k < strlen(stmp); k++) {
    for (m = 0; m <= 9; m++) {
      if (flag[m] && m == (stmp[k] - '0')) {
        return 1;
      }
    }
  }
  return 0;
}
int main() {
  string num;
  while (cin >> num) {
    int i, k, m;
    memset(flag, 0, sizeof(flag));
    for (i = 0; i < num.length(); i++) {
      flag[num[i] - '0'] = 1;
    }
    int number;
    sscanf(num.c_str(), "%d", &number);
    if (number == 1) {
      cout << "1" << endl;
      continue;
    }
    long long ans = 0;
    for (i = 1; i <= sqrt(number); i++) {
      if (number % i != 0) {
        continue;
      }
      if (number / i != i) {
        ans = ans + iscon(i) + iscon(number / i);
      } else
        ans = ans + iscon(i);
    }
    cout << ans << endl;
  }
  return 0;
}
