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 search(int[], int, int);
int aod(int, int[]);
int compare(int[], int, int[], int);
void sort(int a[], int);
void sort(int a[], int l) {
  int i, j;
  for (i = 0; i < l - 1; i++)
    for (j = 0; j < l - 1; j++)
      if (a[j] > a[j + 1]) {
        a[j + 1] += a[j];
        a[j] = a[j + 1] - a[j];
        a[j + 1] = a[j + 1] - a[j];
      }
}
int main() {
  int x, i, i2;
  int d, x_l, i_l;
  int x_a[10], i_a[10];
  scanf("%d", &x);
  x_l = aod(x, x_a);
  sort(x_a, x_l);
  d = 0;
  for (i = 1; i * i <= x; i++) {
    if (x % i == 0) {
      i_l = aod(i, i_a);
      sort(i_a, i_l);
      d += compare(x_a, x_l, i_a, i_l);
      i2 = x / i;
      if (i != i2) {
        i_l = aod(i2, i_a);
        sort(i_a, i_l);
        d += compare(x_a, x_l, i_a, i_l);
      }
    }
  }
  printf("%d", d);
  return 0;
}
int aod(int x, int p[]) {
  int l;
  l = 0;
  for (l = 0; x != 0; l++) {
    p[l] = x % 10;
    x /= 10;
  }
  return l;
}
int compare(int x_a[], int x_l, int i_a[], int i_l) {
  int counter, d;
  for (counter = 0; counter < i_l; counter++)
    if (search(x_a, x_l, i_a[counter])) return 1;
  return 0;
}
int search(int x[10], int l, int a) {
  int low, high, mid;
  low = 0;
  high = l - 1;
  mid = (low + high) / 2;
  while (low <= high) {
    if (a == x[mid])
      return 1;
    else if (a > x[mid])
      low = mid + 1;
    else if (a < x[mid])
      high = mid - 1;
    mid = (low + high) / 2;
  }
  return 0;
}
