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 itoa_cpp(int value, int base) {
  string buf;
  if (base < 2 || base > 16) return buf;
  enum { kMaxDigits = 35 };
  buf.reserve(kMaxDigits);
  int quotient = value;
  do {
    buf += "0123456789abcdef"[std::abs(quotient % base)];
    quotient /= base;
  } while (quotient);
  if (value < 0) buf += '-';
  std::reverse(buf.begin(), buf.end());
  return buf;
}
bool compared(string a, string v) {
  for (int i = 0; i < ((int)(a).size()); i++)
    if (binary_search((v).begin(), (v).end(), a.at(i))) return true;
  return false;
}
int main() {
  int n = ({
    int x;
    scanf("%d", &x);
    x;
  });
  int m = sqrt(n);
  int count = 0;
  string v = itoa_cpp(n, 10);
  sort((v).begin(), (v).end());
  for (int i = 1; i < m + 1; i++) {
    if (n % i == 0) {
      if (i != (n / i)) {
        string a = itoa_cpp(i, 10);
        string b = itoa_cpp(n / i, 10);
        if (compared(a, v)) count++;
        if (compared(b, v)) count++;
      } else {
        string a = itoa_cpp(i, 10);
        count += compared(a, v);
      }
    }
  }
  printf("%d", count);
  return 0;
}
