#include <bits/stdc++.h>
int p[100100], pt, boo[100100], ans, ma[10][10];
std::vector<int> v[10000][6];
void sol(int d) {
  if (d == 6) {
    ans++;
    return;
  }
  int i, j, x = 0, y;
  for (i = 1; i < d; i++) x = x * 10 + ma[d][i];
  for (i = 0; i < v[x][6 - d].size(); i++) {
    y = v[x][6 - d][i];
    for (j = 5; j >= d; j--) {
      ma[d][j] = ma[j][d] = y % 10;
      y /= 10;
    }
    sol(d + 1);
  }
}
int main() {
  int i, j, k;
  for (i = 0; i < 100000; i++) boo[i] = 0;
  for (i = 3; i * i < 100000; i += 2)
    if (!boo[i])
      for (j = i * i; j < 100000; j += 2 * i) boo[j] = 1;
  p[0] = 2;
  pt = 1;
  for (j = 3; j < 100000; j += 2)
    if (!boo[j]) p[pt++] = j;
  for (i = 0; i < pt; i++) {
    v[p[i] / 10][1].push_back(p[i] % 10);
    v[p[i] / 100][2].push_back(p[i] % 100);
    v[p[i] / 1000][3].push_back(p[i] % 1000);
    v[p[i] / 10000][4].push_back(p[i] % 10000);
  }
  int t, x, d, y;
  scanf("%d", &t);
  for (; t; t--) {
    scanf("%d", &x);
    d = 0;
    for (y = x; y; y /= 10) d++;
    for (i = 1; i <= 5; i++)
      for (j = 1; j <= 5; j++) ma[i][j] = 0;
    k = 0;
    for (y = x; y; y /= 10) {
      ma[5 - d + 1][5 - k] = ma[5 - k][5 - d + 1] = y % 10;
      k++;
    }
    ans = 0;
    d = 7 - d;
    sol(d);
    printf("%d\n", ans);
  }
  return 0;
}
