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 n, i;
int D[100], P[100], nrdiv;
int S[100];
int rez;
int prim(int n) {
  int d;
  if (n <= 1) return 0;
  if (n % 2 == 0)
    if (n == 2)
      return 0;
    else
      return 2;
  for (d = 3; d * d <= n; d = d + 2)
    if (n % d == 0) return d;
  return 0;
}
void desc(int n) {
  int d;
  nrdiv = 0;
  while (n > 1) {
    d = prim(n);
    if (d == 0) d = n;
    nrdiv++;
    D[nrdiv] = d;
    P[nrdiv] = 0;
    while (n % d == 0) {
      n = n / d;
      P[nrdiv]++;
    }
  }
}
int ccom(int a, int b) {
  int FA[10], FB[10], i;
  for (i = 0; i <= 9; i++) FA[i] = FB[i] = 0;
  while (a > 0) {
    FA[a % 10]++;
    a = a / 10;
  }
  while (b > 0) {
    FB[b % 10]++;
    b = b / 10;
  }
  for (i = 0; i <= 9; i++)
    if (FA[i] >= 1 && FB[i] >= 1) return 1;
  return 0;
}
void g(int k) {
  int x, i, j;
  if (k == nrdiv) {
    x = 1;
    for (i = 1; i <= nrdiv; i++)
      for (j = 1; j <= S[i]; j++) x = x * D[i];
    if (ccom(x, n) == 1) rez++;
  } else
    for (i = 0; i <= P[k + 1]; i++) {
      S[k + 1] = i;
      g(k + 1);
    }
}
int main() {
  cin >> n;
  desc(n);
  g(0);
  cout << rez;
  return 0;
}
