#include <bits/stdc++.h>
using namespace std;
const int INF = 1000 * 1000 * 1000 + 7;
const double EPS = 1e-9;
int bit_count(int first) {
  return first == 0 ? 0 : 1 + bit_count(first & (first - 1));
}
inline int low_bit(int first) { return first & -first; }
inline int sign(double first) {
  return first < -EPS ? -1 : first > EPS ? 1 : 0;
}
inline int sign(int first) { return (first > 0) - (first < 0); }
inline int getint() {
  int a;
  return scanf("%d", &a) ? a : (fprintf(stderr, "trying to read\n"), -1);
}
inline double getdouble() {
  double a;
  return scanf("%lf", &a) ? a : (fprintf(stderr, "trying to read\n"), -1.0);
}
inline double myrand() {
  return ((double)rand() / RAND_MAX) + ((double)rand() / RAND_MAX / RAND_MAX);
}
vector<bool> isPrime;
int mat[6][6];
vector<bool> sieve(int n) {
  vector<bool> ret(n + 1, true);
  ret[0] = ret[1] = false;
  for (int i = 2; i * i <= n; ++i)
    if (ret[i])
      for (int j = i * i; j <= n; j += i) ret[j] = false;
  return ret;
}
void preprocess() {
  isPrime = sieve(100 * 1000);
  for (int i = (int)0; i < (int)6; ++i)
    for (int j = (int)0; j < (int)6; ++j) mat[i][j] = -1;
}
int numDigs(int first) {
  int ret = 0;
  while (first) {
    ++ret;
    first /= 10;
  }
  return ret;
}
int doit(int n) {
  int ret = 1;
  for (int i = (int)1; i < (int)n; ++i) {
    int cnt = 0;
    for (int j = (int)0; j < (int)10; ++j) {
      mat[i][i] = j;
      int prime = 0;
      for (int t = (int)0; t < (int)n; ++t) {
        prime *= 10;
        prime += mat[i][t];
      }
      if (isPrime[prime]) ++cnt;
    }
    ret *= cnt;
  }
  return ret;
}
int iPrime(int i, int first) {
  mat[i][4] = first;
  for (int s = (int)0; s < (int)10; ++s) {
    mat[i][i] = s;
    int prime = 0;
    for (int t = (int)0; t < (int)5; ++t) {
      prime *= 10;
      prime += mat[i][t];
    }
    if (isPrime[prime]) return true;
    ;
  }
  return false;
}
void myCode() {
  int p = getint();
  int n = numDigs(p);
  for (int i = (int)(n)-1; i >= 0; --i) {
    mat[i][0] = mat[0][i] = p % 10;
    p /= 10;
  }
  int ret = 0;
  if (n == 2)
    ret += doit(n);
  else {
    for (int a = (int)0; a < (int)10; ++a) {
      mat[1][2] = mat[2][1] = a;
      if (n == 3)
        ret += doit(n);
      else {
        for (int b = (int)0; b < (int)10; ++b)
          for (int c = (int)0; c < (int)10; ++c) {
            mat[1][3] = mat[3][1] = b;
            mat[2][3] = mat[3][2] = c;
            if (n == 4)
              ret += doit(n);
            else {
              for (int d = (int)0; d < (int)10; ++d)
                if (iPrime(1, d))
                  for (int e = (int)0; e < (int)10; ++e)
                    if (iPrime(2, e))
                      for (int f = (int)0; f < (int)10; ++f) {
                        mat[1][4] = mat[4][1] = d;
                        mat[2][4] = mat[4][2] = e;
                        mat[3][4] = mat[4][3] = f;
                        ret += doit(n);
                      }
            }
          }
      }
    }
  }
  printf("%d\n", ret);
}
int main() {
  srand(time(NULL));
  preprocess();
  int ttt = getint();
  for (int tt = (int)0; tt < (int)ttt; ++tt) myCode();
  return 0;
}
