#include <bits/stdc++.h>
using namespace std;
void ch_max(int &x, int y) {
  if (x < y) x = y;
}
void ch_min(int &x, int y) {
  if (x > y) x = y;
}
const double pi = acos(-1.0);
const double eps = 1e-9;
const int N = 100005;
int prime[N], tot;
void cal_prime() {
  int i, j, k;
  memset(prime, -1, sizeof(prime));
  for (i = 2; i < N; ++i) {
    if (prime[i] == 0) continue;
    for (j = i + i; j < N; j += i) prime[j] = 0;
  }
  tot = 0;
  for (i = 2; i < N; ++i) {
    if (prime[i]) prime[tot++] = i;
  }
}
char str[10][10];
int len, ans;
int a[N][10], b[N];
void cal_a() {
  int i, j, k;
  for (i = 0; i < tot; ++i) {
    int tmp = prime[i];
    for (j = 0; j < 10; ++j) {
      a[i][j] = tmp % 10;
      tmp /= 10;
    }
  }
  for (i = 0; i < N; ++i) {
    b[i] = lower_bound(prime, prime + tot, i) - prime;
  }
}
void solve(int t) {
  int i, j, k;
  if (t == len) {
    ans++;
    return;
  }
  int tmp = 0;
  for (i = 0; i < t; ++i) {
    tmp = tmp * 10 + str[t][i] - '0';
  }
  int t0 = 1;
  for (; i < len; ++i) {
    tmp *= 10;
    t0 *= 10;
  }
  int l = b[tmp];
  int r = b[tmp + t0];
  if (t == len - 1) {
    ans += r - l;
    return;
  }
  for (i = l; i < r; ++i) {
    for (k = 0, j = len - 1; j >= t; --j) {
      str[t][j] = a[i][k++] + '0';
    }
    for (j = t + 1; j < len; ++j) str[j][t] = str[t][j];
    solve(t + 1);
  }
}
int main() {
  int i, j, k, t, nc = 0;
  int t0, t1, t2, t3;
  cal_prime();
  cal_a();
  scanf("%d", &t);
  while (t--) {
    memset(str, 0, sizeof(str));
    scanf("%s", str[0]);
    len = strlen(str[0]);
    ans = 0;
    for (i = 1; i < len; ++i) str[i][0] = str[0][i];
    solve(1);
    printf("%d\n", ans);
  }
  return 0;
}
