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;
long long n, N;
long long d[31] = {}, num[31] = {};
int top, ans;
bool used[11] = {};
void solve(int now, int sum) {
  int p = 1;
  if (now == top) {
    while (sum) {
      if (used[sum % 10]) {
        ans++;
        break;
      }
      sum /= 10;
    }
    return;
  }
  for (int i = 0; i <= num[now]; i++) {
    solve(now + 1, sum * p);
    p *= d[now];
  }
}
int main() {
  while (cin >> n) {
    N = n;
    while (N) {
      used[N % 10] = 1;
      N /= 10;
    }
    ans = top = 0;
    if (n % 2 == 0) {
      d[0] = 2;
      while (n % 2 == 0) num[0]++, n /= 2;
      top++;
    }
    for (long long i = 3; i * i <= n; i += 2) {
      if (n % i == 0) {
        d[top] = i;
        while (n % i == 0) {
          n /= i;
          num[top]++;
        }
        top++;
      }
    }
    if (n > 1) d[top] = n, num[top] = 1, top++;
    solve(0, 1);
    printf("%d\n", ans);
  }
}
