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>
static const long long LLMAX = 0x7fffffffffffffffLL;
static const int IMAX = 0x7fffffff;
using namespace std;
const static int maxn = (int)1e7;
bool isp[maxn];
int prime[maxn], lp;
void gen_prime() {
  int i, j;
  memset(isp, true, sizeof isp);
  isp[0] = isp[1] = false;
  lp = 0;
  for (i = 2; i < maxn; ++i) {
    if (isp[i]) prime[lp++] = i;
    for (j = 0; j < lp && prime[j] * i < maxn; ++j) {
      isp[prime[j] * i] = false;
      if (i % prime[j] == 0) break;
    }
  }
}
vector<pair<int, int> > getPrimeFactors(int n) {
  vector<pair<int, int> > ret;
  int sqrtn = (int)sqrt(static_cast<double>(n));
  for (int i = 0; i < maxn && prime[i] <= sqrtn; ++i) {
    if (n % prime[i] == 0) {
      int cnt = 0;
      while (n % prime[i] == 0) {
        cnt++;
        n /= prime[i];
      }
      ret.push_back(make_pair(prime[i], cnt));
    }
  }
  if (n != 1) {
    ret.push_back(make_pair(n, 1));
  }
  return ret;
}
bool check(int v, int n) {
  bool vm[10];
  memset(vm, false, sizeof vm);
  while (v) {
    vm[v % 10] = true;
    v /= 10;
  }
  while (n) {
    if (vm[n % 10]) return true;
    n /= 10;
  }
  return false;
}
int n;
int cnt;
void cpt(vector<pair<int, int> >& v, int mul, int c) {
  if (c == v.size()) {
    if (check(mul, n)) {
      cnt++;
    }
    return;
  }
  cpt(v, mul, c + 1);
  for (int i = 1; i <= v[c].second; ++i) {
    mul *= v[c].first;
    cpt(v, mul, c + 1);
  }
}
int main() {
  gen_prime();
  while (~scanf("%d", &n)) {
    if (n == 1) {
      printf("1\n");
      continue;
    }
    vector<pair<int, int> > v = getPrimeFactors(n);
    cnt = 0;
    cpt(v, 1, 0);
    printf("%d\n", cnt);
  }
  return 0;
}
