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 main(int argc, char const *argv[]) {
  int x;
  cin >> x;
  int i = 1;
  int c = 0;
  stringstream ss1;
  ss1 << x;
  string str1 = ss1.str();
  int flag = 0;
  while (i < sqrt(x)) {
    flag = 0;
    int w = i;
    for (int q = 0; q < 2; ++q) {
      flag = 0;
      if (x % w == 0) {
        stringstream ss;
        ss << w;
        string str = ss.str();
        for (int k = 0; k < str1.length(); ++k) {
          for (int j = 0; j < str.length(); ++j) {
            if (str[j] == str1[k]) {
              c++;
              flag = 1;
              break;
            }
          }
          if (flag == 1) break;
        }
      }
      w = x / i;
    }
    i++;
  }
  flag = 0;
  if (i * i == x) {
    stringstream ss;
    ss << i;
    string str = ss.str();
    for (int k = 0; k < str1.length(); ++k) {
      for (int j = 0; j < str.length(); ++j) {
        if (str[j] == str1[k]) {
          c++;
          flag = 1;
          break;
        }
      }
      if (flag == 1) break;
    }
  }
  cout << c << endl;
  return 0;
}
