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;
const int IINF = 1 << 28;
const double INF = 1e30;
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, -1, 0, 1};
int main() {
  bool isexist[10] = {false};
  set<int> s1, s2;
  int x, y;
  cin >> x;
  y = x;
  for (int i = 1; i * i <= x; ++i) {
    if (x % i == 0) {
      s1.insert(i);
    }
  }
  while (y > 0) {
    isexist[y % 10] = true;
    y /= 10;
  }
  int cnt = 0;
  for (set<int>::iterator itr = s1.begin(); itr != s1.end(); ++itr) {
    int tmp = *itr;
    bool flag = false;
    while (tmp > 0) {
      if (isexist[tmp % 10]) {
        flag = true;
        break;
      }
      tmp /= 10;
    }
    if (flag) {
      ++cnt;
    }
    if (*itr != x / *itr) {
      s2.insert(x / *itr);
    }
  }
  for (set<int>::iterator itr = s2.begin(); itr != s2.end(); ++itr) {
    int tmp = *itr;
    bool flag = false;
    while (tmp > 0) {
      if (isexist[tmp % 10]) {
        flag = true;
        break;
      }
      tmp /= 10;
    }
    if (flag) {
      ++cnt;
    }
  }
  cout << cnt << endl;
}
