#include <bits/stdc++.h>
using namespace std;
void ASS(bool b) {
  if (!b) {
    ++*(int*)0;
  }
}
#pragma comment(linker, "/STACK:106777216")
vector<int> p;
vector<char> IsPrime;
int n;
int pw10[8];
int a[8][8];
int ans = 0;
int TT[8][100000];
void rec(int x, int y, int tt) {
  if (x == n) {
    ans += tt;
    return;
  }
  if (y == n) {
    int z = 0;
    for (int i = 0; i < (int)(n); i++) z = z * 10 + a[x][i];
    rec(x + 1, x + 2, tt * TT[n - 1 - x][z]);
    return;
  }
  for (int i = 0; i < (int)(10); i++) {
    a[x][y] = a[y][x] = i;
    rec(x, y + 1, tt);
  }
}
void Solve(int x) {
  n = 0;
  while (x) {
    a[0][n] = x % 10;
    x /= 10;
    n++;
  }
  reverse(a[0], a[0] + n);
  for (int i = 0; i < (int)(n); i++) a[i][0] = a[0][i];
  ans = 0;
  rec(1, 2, 1);
  cout << ans << endl;
}
int main() {
  vector<char>& a = IsPrime;
  a.assign(100000, 1);
  a[0] = a[1] = 0;
  pw10[0] = 1;
  for (int i = 0; i < (int)(6); i++) pw10[i + 1] = pw10[i] * 10;
  for (int i = 2; i < (int)a.size(); i++)
    if (a[i]) {
      p.push_back(i);
      for (int j = i * 2; j < (int)a.size(); j += i) a[j] = 0;
    }
  for (int z = 0; z < (int)(100000); z++) {
    static int ar[8];
    for (int i = 0; i < (int)(5); i++) {
      int curDig = (z / pw10[i]) % 10;
      if (curDig == 0) {
        for (int d = 0; d < (int)(10); d++) {
          int zz = z + (d - curDig) * pw10[i];
          TT[i][z] += IsPrime[zz];
        }
      }
    }
  }
  int t;
  cin >> t;
  for (int i = 0; i < (int)(t); i++) {
    int x;
    cin >> x;
    Solve(x);
  }
  return 0;
}
