#include <bits/stdc++.h>
using namespace std;
bool check[100010];
int f[10][10], sum[10], n, ans, mi[10], cut[5][10][10][10][10];
char str[10];
void Dfs2(int k) {
  if (k > n) {
    ans++;
    return;
  }
  for (int i = 0; i <= 9; i++)
    if (check[sum[k] + i * mi[n - k]] == false) {
      f[k][k] = i;
      Dfs2(k + 1);
    }
}
void Dfs(int x, int y, int z) {
  if (x == n) {
    if (n == 5)
      ans += z * cut[4][f[5][1]][f[5][2]][f[5][3]][f[5][4]];
    else
      Dfs2(2);
    return;
  }
  for (int i = 0; i <= 9; i++) {
    f[x][y] = f[y][x] = i;
    sum[x] += i * mi[n - y];
    sum[y] += i * mi[n - x];
    if (y == n) {
      if (n == 5) {
        int p;
        switch (x) {
          case 2:
            p = cut[1][f[2][1]][f[2][3]][f[2][4]][f[2][5]];
            break;
          case 3:
            p = cut[2][f[3][1]][f[3][2]][f[3][4]][f[3][5]];
            break;
          case 4:
            p = cut[3][f[4][1]][f[4][2]][f[4][3]][f[4][5]];
            break;
        }
        if (p) Dfs(x + 1, x + 2, z * p);
      } else
        Dfs(x + 1, x + 2, z);
    } else
      Dfs(x, y + 1, z);
    sum[x] -= i * mi[n - y];
    sum[y] -= i * mi[n - x];
  }
}
int main() {
  check[0] = check[1] = true;
  for (int i = 2; i < 100000; i++)
    if (check[i] == false)
      for (int j = i + i; j < 100000; j += i) check[j] = true;
  for (int i = 0; i < 10; i++)
    for (int j = 0; j < 10; j++)
      for (int p = 0; p < 10; p++)
        for (int k = 0; k < 10; k++)
          for (int q = 0; q < 10; q++)
            if (check[i * 10000 + j * 1000 + p * 100 + k * 10 + q] == false) {
              cut[1][i][p][k][q]++;
              cut[2][i][j][k][q]++;
              cut[3][i][j][p][q]++;
              cut[4][i][j][p][k]++;
            }
  int t;
  scanf("%d\n", &t);
  for (int i = 1; i <= t; i++) {
    scanf("%s\n", str);
    n = strlen(str);
    mi[0] = 1;
    for (int i = 1; i <= n; i++) mi[i] = mi[i - 1] * 10, sum[i] = 0;
    for (int i = 1; i <= n; i++) {
      f[1][i] = f[i][1] = str[i - 1] - '0';
      sum[1] += f[1][i] * mi[n - i];
      if (i != 1) sum[i] += f[1][i] * mi[n - 1];
    }
    ans = 0;
    Dfs(2, 3, 1);
    printf("%d\n", ans);
  }
  return 0;
}
