#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
int T, n, tot, bit[10], a[10][10], f2[10][10][10][10], f3[10][10][10][10],
    f4[10][10][10][10], f5[10][10][10][10];
bool isp[N];
long long ans;
void sieve() {
  memset(isp, 1, sizeof(isp));
  isp[0] = 0;
  isp[1] = 0;
  for (int i = int(2); i <= int(N - 1); ++i) {
    for (int j = i + i; j < N; j += i) isp[j] = 0;
  }
}
void dfs(int x, int y) {
  if (x > tot) {
    int flag = 1;
    for (int i = int(2); i <= int(tot); ++i) {
      int num = 0;
      for (int j = int(1); j <= int(tot); ++j) num = num * 10 + a[i][j];
      if (isp[num] == 0) {
        flag = 0;
        break;
      }
    }
    ans += flag;
    return;
  }
  int xx = x, yy = y + 1;
  if (yy > tot) xx = yy = x + 1;
  for (int i = int(0); i <= int(9); ++i) {
    a[x][y] = a[y][x] = i;
    dfs(xx, yy);
  }
}
void dfs2(int x, int y) {
  if (x >= tot) {
    long long ret = 1;
    ret = f2[a[2][1]][a[2][3]][a[2][4]][a[2][5]];
    ret *= f3[a[3][1]][a[3][2]][a[3][4]][a[3][5]];
    ret *= f4[a[4][1]][a[4][2]][a[4][3]][a[4][5]];
    ret *= f5[a[5][1]][a[5][2]][a[5][3]][a[5][4]];
    ans += ret;
    return;
  }
  int xx = x, yy = y + 1;
  if (yy > tot) {
    xx = x + 1;
    yy = xx + 1;
  }
  if (y != 5)
    for (int i = int(0); i <= int(9); ++i) {
      a[x][y] = a[y][x] = i;
      dfs2(xx, yy);
    }
  else {
    a[x][y] = a[y][x] = 2;
    dfs2(xx, yy);
    for (int i = 1; i <= 9; i += 2) {
      a[x][y] = a[y][x] = i;
      dfs2(xx, yy);
    }
  }
}
int main() {
  sieve();
  for (int p = int(2); p <= int(99999); ++p)
    if (isp[p]) {
      int t1 = p / 10000;
      int t2 = (p / 1000) % 10;
      int t3 = (p / 100) % 10;
      int t4 = (p / 10) % 10;
      int t5 = p % 10;
      f2[t1][t3][t4][t5]++;
      f3[t1][t2][t4][t5]++;
      f4[t1][t2][t3][t5]++;
      f5[t1][t2][t3][t4]++;
    }
  cin >> T;
  while (T--) {
    cin >> n;
    tot = 0;
    ans = 0;
    while (n) {
      bit[++tot] = n % 10;
      n /= 10;
    }
    for (int i = int(1); i <= int(tot); ++i)
      for (int j = int(1); j <= int(tot); ++j) a[i][j] = -1;
    for (int i = int(1); i <= int(tot); ++i)
      a[1][i] = a[i][1] = bit[tot + 1 - i];
    if (tot <= 4)
      dfs(2, 2);
    else
      dfs2(2, 3);
    cout << ans << endl;
  }
}
