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;
inline void in(int &x) { scanf("%d", &x); }
inline void in(int &x, int &y) { scanf("%d %d", &x, &y); }
inline void out(int x) { printf("%d ", x); }
inline void outln(int x) { printf("%d\n", x); }
inline int _abs(int x) { return x > 0 ? x : -x; }
int n;
vector<int> find_digs(int n) {
  vector<int> digs(10);
  while (n) {
    digs[n % 10]++;
    n /= 10;
  }
  return digs;
}
bool cross(vector<int> &a, vector<int> &b) {
  for (int i = 0; i < a.size(); ++i) {
    if (a[i] && b[i]) return true;
  }
  return false;
}
int main() {
  int x, X;
  cin >> x;
  vector<int> xd = find_digs(x);
  int len = sqrt(x + 0.0);
  int cnt = 0;
  for (int cur = 1; cur <= len; ++cur) {
    if (x % cur == 0) {
      vector<int> curd = find_digs(cur);
      if (cross(xd, curd)) ++cnt;
      if (cur != x / cur) {
        curd = find_digs(x / cur);
        if (cross(xd, curd)) ++cnt;
      }
    }
  }
  cout << cnt;
  return 0;
}
