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>
int pri[100100];
int p[100100];
int cnt[10];
int tot;
void Prime() {
  tot = 0;
  memset(p, 0, sizeof(p));
  int i = 2;
  while (i < 100000) {
    while (p[i]) i++;
    pri[tot++] = i;
    int j = i;
    while (j < 100000) {
      p[j] = 1;
      j += i;
    }
  }
  tot--;
  return;
}
bool check(int x, int d) {
  memset(cnt, 0, sizeof(cnt));
  while (x) {
    cnt[x % 10]++;
    x /= 10;
  }
  while (d) {
    if (cnt[d % 10] > 0) return 1;
    d /= 10;
  }
  return 0;
}
int main() {
  int x;
  Prime();
  scanf("%d", &x);
  int ans = 1;
  if (x != 1 && check(x, 1)) ans++;
  for (int i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      if (i * i == x) {
        if (check(x, i)) ans++;
      } else {
        if (check(x, i)) ans++;
        if (check(x, x / i)) ans++;
      }
    }
  }
  printf("%d\n", ans);
  return 0;
}
