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;
const int maxn = 100010;
int pri[maxn];
int tot;
int p[maxn];
int cnt[maxn];
void init(int x) {
  tot = 0;
  memset(cnt, 0, sizeof(cnt));
  int tmp = x;
  for (int i = 2; i <= (int)sqrt(1.0 * tmp); i++) {
    if (x % i == 0) {
      p[++tot] = i;
      while (x % i == 0) {
        cnt[tot]++;
        x /= i;
      }
      if (x == 1) break;
      if (x < 100000 && !pri[x]) {
        p[++tot] = x;
        cnt[tot] = 1;
        return;
      }
    }
  }
  if (x != 1) p[++tot] = x, cnt[tot] = 1;
}
int ans;
int n;
bool ok(int x, int y) {
  int flag[10];
  memset(flag, 0, sizeof(flag));
  for (; y; y /= 10) flag[y % 10]++;
  for (; x; x /= 10)
    if (flag[x % 10]) return true;
  return false;
}
void dfs(int dep, int now) {
  if (dep == tot + 1) {
    if (ok(now, n)) ans++;
    return;
  }
  dfs(dep + 1, now);
  for (int i = 1; i <= cnt[dep]; i++) {
    dfs(dep + 1, now * (int)pow(p[dep] * 1.0, i));
  }
}
int main() {
  memset(pri, 0, sizeof(pri));
  for (int i = 2; i <= 100000; i++) {
    for (int j = 2 * i; j <= 100000; j += i) {
      pri[j] = 1;
    }
  }
  while (scanf("%d", &n) != EOF) {
    init(n);
    ans = 0;
    dfs(1, 1);
    printf("%d\n", ans);
  }
}
