#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double PI = acos(-1.0);
const int maxn = 100000 + 10;
bool vis[maxn];
vector<int> G[6][maxn];
int base10[10];
void init() {
  memset(vis, false, sizeof(vis));
  vis[0] = vis[1] = true;
  int m = sqrt(maxn + 0.5);
  for (int i = 2; i <= m; i++)
    for (int j = i * i; j <= 100000; j += i) vis[j] = true;
  int sz = 0;
  for (int i = 2; i <= 100000; i++)
    if (!vis[i]) sz++;
  for (int i = 1; i < 100000; i++)
    if (!vis[i]) {
      int base = 10, x = i;
      for (int j = 1; j <= 5; j++) {
        x -= x % base;
        G[j][x].push_back(i);
        base *= 10;
      }
    }
}
int n;
char s[maxn];
char A[10][10];
long long ans;
long long d[maxn][5];
void dfs(int cnt) {
  int x = 0;
  for (int i = 0; i < cnt; i++) x = x * 10 + A[cnt][i] - '0';
  for (int i = cnt; i < n; i++) x *= 10;
  if (cnt == n - 1) {
    ans += G[n - cnt][x].size();
    return;
  } else {
    int len = n - cnt;
    for (int i = 0; i < G[len][x].size(); i++) {
      int v = G[len][x][i], ttt = v;
      for (int j = cnt, k = n - 1; j < n; j++, k--) {
        int tmp = v % 10;
        A[cnt][k] = A[k][cnt] = tmp + '0';
        v /= 10;
      }
      dfs(cnt + 1);
    }
  }
}
int main() {
  init();
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%s", s);
    n = strlen(s);
    for (int i = 0; i < n; i++) A[i][0] = s[i];
    for (int i = 0; i < n; i++) A[0][i] = s[i];
    ans = 0;
    dfs(1);
    printf("%d\n", ans);
  }
  return 0;
}
