#include <bits/stdc++.h>
using namespace std;
int r[100000], p[100000], b[5], w[5] = {1, 10, 100, 1000, 10000}, n;
int dfs(int x) {
  int a, t, q, y, f;
  int o;
  y = w[n - x];
  q = f = b[x];
  o = 0;
  while (1) {
    q = p[q];
    if (q >= f + y) break;
    t = q;
    for (a = n - 1; a > x; a--) {
      b[a] = b[a] - b[a] % w[n - x] + t % 10 * w[n - x - 1];
      t /= 10;
    }
    if (x == n - 1)
      o++;
    else
      o += dfs(x + 1);
    q++;
  }
  return o;
}
int main() {
  int a, s, t, i, x[5];
  for (a = 0; a < 100000; a++) r[a] = 1;
  r[0] = 0;
  r[1] = 0;
  for (a = 2; a < 100000; a++) {
    if (r[a] == 0) continue;
    for (s = 2 * a; s < 100000; s += a) r[s] = 0;
  }
  p[99999] = 100000;
  for (a = 100000 - 2; a >= 0; a--) {
    if (r[a] == 1)
      p[a] = a;
    else
      p[a] = p[a + 1];
  }
  int T, N;
  scanf("%d", &N);
  for (T = 0; T < N; T++) {
    scanf("%d", &i);
    t = i;
    n = 0;
    while (t > 0) {
      x[n] = t % 10;
      n++;
      t /= 10;
    }
    b[0] = i;
    for (a = 1; a < n; a++) {
      b[a] = x[n - a - 1] * w[n - 1];
    }
    printf("%d\n", dfs(1));
  }
  return 0;
}
