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 b[10];
bool is(int n) {
  for (; n; n /= 10)
    if (b[n % 10]) return 1;
  return 0;
}
int main() {
  int i, n, j;
  for (scanf("%d", &n), i = n; i; b[i % 10] = 1, i /= 10)
    ;
  for (j = 0, i = 1; i * i < n; i++)
    if (n % i == 0) j += is(i) + is(n / i);
  j += i * i == n && is(i);
  printf("%d\n", j);
  return 0;
}
