#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e5 + 5;
bool A[MAX_N];
std::vector<int> mp[5][MAX_N];
int a[6][6], len;
void init() {
  for (int i = 2; i < MAX_N; i++)
    if (!A[i]) {
      int tmp = i / 10;
      for (int j = 1; j < 5; j++) {
        mp[j][tmp].push_back(i);
        tmp /= 10;
      }
      if (1ll * i * i > MAX_N) continue;
      for (int j = i * i; j < MAX_N; j += i) A[j] = 1;
    }
}
int dfs(int now) {
  int x = 0, sum = 0;
  for (int i = 0; i < now; i++) x = x * 10 + a[now][i];
  if (now == len - 1) return mp[1][x].size();
  for (int i = 0; i < mp[len - now][x].size(); i++) {
    int tmp = mp[len - now][x][i];
    for (int j = len - 1; j >= now; j--) {
      a[j][now] = a[now][j] = tmp % 10;
      tmp /= 10;
    }
    sum += dfs(now + 1);
  }
  return sum;
}
void solve() {
  char s[6];
  scanf("%s", s);
  len = strlen(s);
  for (int i = 0; i < len; i++) a[i][0] = a[0][i] = s[i] - '0';
  printf("%d\n", dfs(1));
}
int main() {
  init();
  int cas;
  scanf("%d", &cas);
  while (cas--) {
    solve();
  }
  return 0;
}
