#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:0x8000000")
using namespace std;
long double const PI = 3.1415926535897932384626433832795;
template <class T>
inline T sqr(const T &a) {
  return a * a;
}
int const N = 101000;
int p[N], L[N];
char s[6][6];
int n, res;
int st[N];
char num[N][6];
int pw[10];
void calc(int x = 1) {
  if (x == n) {
    ++res;
    return;
  }
  int k = 0, q = pw[n - x];
  for (int i = 0; i < x; ++i) k = k * 10 + s[x][i] - '0';
  int y = st[k * q], r = (k + 1) * q;
  for (; p[y] < r; ++y) {
    int c = p[y];
    for (int i = n - 1; i >= x; --i) s[i][x] = s[x][i] = num[c][n - 1 - i];
    calc(x + 1);
  }
}
int main() {
  pw[0] = 1;
  for (int i = 1; i < 10; ++i) pw[i] = pw[i - 1] * 10;
  for (int i = 0; i < N; ++i) {
    int c = i;
    for (int j = 0; j < 6; ++j) {
      num[i][j] = c % 10 + '0';
      c /= 10;
    }
  }
  for (int i = 2; i < N; ++i) {
    if (!L[i]) p[++p[0]] = i, L[i] = p[0];
    for (int j = 1; j <= L[i] && i * p[j] < N; ++j) L[i * p[j]] = j;
  }
  for (int i = 0; i < N; ++i) st[i] = lower_bound(p + 1, p + p[0], i) - p;
  int nt;
  cin >> nt;
  for (; nt; --nt) {
    memset(s, 0, sizeof s);
    scanf("%s", s[0]);
    n = strlen(s[0]);
    for (int i = 0; i < n; ++i) s[i][0] = s[0][i];
    res = 0;
    calc();
    cout << res << endl;
  }
  return 0;
}
