#include <bits/stdc++.h>
using namespace std;
template <class T>
void miz(T &a, T b) {
  if (b < a) a = b;
}
template <class T>
void maz(T &a, T b) {
  if (b > a) a = b;
}
template <class T>
void clear(T &x) {
  T t;
  x.swap(t);
}
template <class T>
T gcd(T a, T b) {
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}
void sieve(int n, vector<int> &plst) {
  int i, j, k, t;
  vector<int> pf(1 + n);
  fill(pf.begin(), pf.end(), -1);
  for (i = 2; i <= n; i++) {
    if (pf[i] < 0) {
      pf[i] = plst.size();
      plst.push_back(i);
    }
    t = pf[i];
    for (j = 0; j <= t && (k = plst[j] * i) <= n; j++) pf[k] = j;
  }
}
const int PMAX = 99999;
const int LMAX = 5;
int L, ans;
int M[LMAX][LMAX];
vector<int> candidate[1 + PMAX][LMAX];
int S[1 + PMAX][LMAX];
int get(int r, int c) {
  int i, ret = 0;
  for (i = 0; i < c; i++) ret = ret * 10 + M[r][i];
  return ret;
}
void dfs(int dep) {
  if (dep == L) {
    ans++;
    return;
  }
  int i;
  vector<int>::iterator it;
  vector<int> &c = candidate[get(dep, dep)][L - dep];
  for (it = c.begin(); it != c.end(); ++it) {
    for (i = dep; i < L; i++) M[i][dep] = S[*it][LMAX - L + i];
    for (i = dep + 1; i < L; i++)
      if (candidate[get(i, dep + 1)][L - (dep + 1)].empty()) break;
    if (i == L) dfs(dep + 1);
  }
}
int solve(int H) {
  for (int i = L - 1; i >= 0; i--) {
    M[0][i] = H % 10;
    M[i][0] = H % 10;
    H /= 10;
  }
  ans = 0;
  dfs(1);
  return ans;
}
void build() {
  vector<int> plst;
  sieve(PMAX, plst);
  for (vector<int>::iterator it = plst.begin(); it != plst.end(); ++it) {
    int p = *it;
    int q = p;
    for (int i = 0; i < LMAX; i++) {
      candidate[q][i].push_back(p);
      q /= 10;
    }
    q = p;
    for (int i = LMAX - 1; i >= 0; i--) {
      S[p][i] = q % 10;
      q /= 10;
    }
  }
}
int length(int x) {
  int i;
  for (i = 0; x; i++) x /= 10;
  return i;
}
int main() {
  int T, H;
  build();
  cin >> T;
  while (T--) {
    cin >> H;
    L = length(H);
    cout << solve(H) << endl;
  }
  return 0;
}
