#include <bits/stdc++.h>
#pragma comment(linker, "/stack:64000000")
using namespace std;
template <typename X>
inline X abs(const X& a) {
  return a < 0 ? -a : a;
}
template <typename X>
inline X sqr(const X& a) {
  return a * a;
}
const int INF = INT_MAX / 2;
const long double EPS = 1e-9;
const long double PI = 3.1415926535897932384626433832795;
const int N = 100 * 1000 + 3;
int first;
inline bool read() { return (scanf("%d", &first) == 1); }
inline string toStr(int first) {
  stringstream ss;
  ss << first;
  string ans;
  ss >> ans;
  return ans;
}
int ans = 0;
int a[6][6];
int n;
bool pr[N];
inline bool can(int idx, int cur) {
  int st = 1;
  int val = 0;
  for (int i = int(n) - 1; i >= 0; i--) {
    if (i == idx)
      val += st * cur;
    else
      assert(a[idx][i] != -1), val += st * a[idx][i];
    st *= 10;
  }
  return pr[val];
}
inline int getCnt(int i) {
  int cnt = 0;
  for (int cur = 0; cur < int(10); cur++)
    if (can(i, cur)) cnt++;
  return cnt;
}
void solve(int first, int second) {
  if (first == n - 1) {
    int res = 1;
    for (int i = 1; i <= int(n - 1); i++) {
      int cnt = getCnt(i);
      res *= cnt;
    }
    ans += res;
    return;
  }
  if (getCnt(first - 1) == 0) return;
  int nx = first, ny = second + 1;
  if (ny >= n) nx = first + 1, ny = nx + 1;
  for (int cur = 0; cur < int(10); cur++) {
    a[first][second] = a[second][first] = cur;
    solve(nx, ny);
    a[first][second] = a[second][first] = -1;
  }
}
inline void solve() {
  assert(pr[first]);
  string cur = toStr(first);
  n = int((cur).size());
  assert(n >= 2 && n <= 5);
  memset(a, -1, sizeof(a));
  for (int i = 0; i < int(n); i++) {
    a[0][i] = cur[i] - '0';
    a[i][0] = cur[i] - '0';
  }
  ans = 0;
  solve(1, 2);
  printf("%d\n", ans);
}
inline void preCalc() {
  memset(pr, true, sizeof(pr));
  pr[0] = pr[1] = false;
  for (int i = 2; i < N; i++) {
    if (!pr[i]) continue;
    for (int j = i + i; j < N; j += i) pr[j] = false;
  }
}
int main() {
  preCalc();
  int testCnt;
  assert(scanf("%d", &testCnt) == 1);
  for (int test = 0; test < int(testCnt); test++) {
    assert(read());
    solve();
  }
  return 0;
}
