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;
int X, N[10];
char S[100], T[100];
bool ok(int q) {
  int n = sprintf(T, "%d", q);
  for (int i = 0; i < n; ++i)
    if (N[T[i] - '0']) return true;
  return false;
}
int main() {
  while (cin >> X) {
    fill(N, N + 10, 0);
    int n = sprintf(S, "%d", X);
    for (int i = 0; i < n; ++i) N[S[i] - '0']++;
    int X2 = (int)floor(sqrt((double)X)), C = 0;
    for (int i = 1; i <= X2; ++i) {
      int p = X / i;
      if (p * i != X) continue;
      if (ok(i)) ++C;
      if (p != i && ok(p)) ++C;
    }
    cout << C << endl;
  }
}
