#include <bits/stdc++.h>
using namespace std;
bool prim[100000];
vector<int> pr;
int K;
char feld[5][5];
int erg = 0;
int st[100000];
void suche(int j) {
  if (j == K) {
    erg++;
    return;
  }
  int h = 0;
  for (int i = 0; i < j; i++) h = 10 * h + feld[j][i];
  int hn = h + 1;
  for (int i = 0; i < K - j; i++) {
    h *= 10;
    hn *= 10;
  }
  for (int ip = st[h]; ip < (int)pr.size() && pr[ip] < hn; ip++) {
    int r = pr[ip];
    for (int k = 0; k < K - j; k++) {
      feld[j][K - k - 1] = feld[K - k - 1][j] = r % 10;
      r /= 10;
    }
    suche(j + 1);
  }
}
int main() {
  prim[1] = false;
  for (int p = 2; p < 100000; p++) prim[p] = true;
  for (int p = 2; p < 100000; p++) {
    if (prim[p]) pr.push_back(p);
    if (prim[p] && p < 1000)
      for (int k = p * p; k < 100000; k += p) prim[k] = false;
  }
  int ip = 0;
  for (int i = 0; i < 100000; i++) {
    while (ip < (int)pr.size() && pr[ip] < i) ip++;
    st[i] = ip;
  }
  int T;
  scanf("%d", &T);
  for (int i = 0; i < T; i++) {
    int p;
    scanf("%d", &p);
    K = 0;
    int r = p;
    while (r) {
      r /= 10;
      K++;
    }
    r = p;
    for (int i = 0; i < K; i++) {
      feld[0][K - i - 1] = feld[K - i - 1][0] = r % 10;
      r /= 10;
    }
    erg = 0;
    suche(1);
    printf("%d\n", erg);
  }
  return 0;
}
