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;
string tostring(long long n) {
  ostringstream ss;
  ss << n;
  return ss.str();
}
long long tonumber(string str) {
  stringstream ss;
  ss << str;
  long long n;
  ss >> n;
  return n;
}
bool issame(int a, int b) {
  while (a) {
    int temp = b;
    while (temp) {
      if (a % 10 == temp % 10) return true;
      temp /= 10;
    }
    a /= 10;
  }
  return false;
}
int main() {
  int n, sum = 0;
  while (cin >> n) {
    int num = 0;
    for (int r = 1; r <= sqrt(n); r++) {
      if (n % r == 0) {
        if (issame(r, n)) num++;
        if (r != n / r && issame(n / r, n)) num++;
      }
    }
    cout << num << endl;
  }
  return 0;
}
