#include <bits/stdc++.h>
using namespace std;
template <class X, class Y>
bool minimize(X &x, const Y &y) {
  X eps = 1e-9;
  if (x > y + eps) {
    x = y;
    return true;
  } else
    return false;
}
template <class X, class Y>
bool maximize(X &x, const Y &y) {
  X eps = 1e-9;
  if (x + eps < y) {
    x = y;
    return true;
  } else
    return false;
}
template <class T>
T Abs(const T &x) {
  return (x < 0 ? -x : x);
}
vector<int> primes[5 + 1][(1LL << ((5) << 2)) + 1];
bool notPrime[100100];
int toHexa(int x, int numDigit) {
  int res = 0;
  for (int love = 0, _n = (numDigit); love < _n; love++) {
    res = (res << 4) ^ (x % 10);
    x /= 10;
  }
  return x > 0 ? -1 : res;
}
void prepare(void) {
  for (int i = 0, _n = (2); i < _n; i++) notPrime[i] = true;
  for (int i = (2), _b = (100100 - 1); i <= _b; i++)
    if (!notPrime[i])
      for (int j = 2 * i; j < 100100; j += i) notPrime[j] = true;
  for (int i = (2), _b = (100100 - 1); i <= _b; i++)
    if (!notPrime[i])
      for (int length = (1), _b = (5); length <= _b; length++) {
        int code = toHexa(i, length);
        if (code < 0) continue;
        for (int mask = 0, _n = ((1LL << (length))); mask < _n; mask++) {
          int newCode = code;
          for (int i = 0, _n = (length); i < _n; i++)
            if ((((mask) >> (i)) & 1))
              newCode =
                  (((newCode) & ~(15 << ((i) << 2))) ^ ((10) << ((i) << 2)));
          primes[length][newCode].push_back(code);
        }
      }
}
int res;
void backtrack(vector<int> &state, int filled) {
  int numRow = state.size();
  if (__builtin_popcountll(filled) == numRow) {
    res++;
    return;
  }
  int row = -1, numCandidate = 100100;
  if (!(((filled) >> (numRow - 1)) & 1)) {
    row = numRow - 1;
    numCandidate = primes[numRow][state[row]].size();
  } else {
    for (int i = 0, _n = (numRow); i < _n; i++)
      if (!(((filled) >> (i)) & 1)) {
        int tmpCandidate = primes[numRow][state[i]].size();
        if (minimize(numCandidate, tmpCandidate)) row = i;
      }
  }
  if (numCandidate == 0) return;
  if (__builtin_popcountll(filled) == numRow - 1) {
    res += numCandidate;
    return;
  }
  int oldState = state[row];
  vector<int> &candidates = primes[numRow][oldState];
  for (__typeof((candidates).begin()) it = (candidates).begin();
       it != (candidates).end(); it++) {
    for (int j = 0, _n = (numRow); j < _n; j++) {
      state[row] = (((state[row]) & ~(15 << ((j) << 2))) ^
                    (((((*it) >> ((j) << 2)) & 15)) << ((j) << 2)));
      state[j] = (((state[j]) & ~(15 << ((row) << 2))) ^
                  (((((*it) >> ((j) << 2)) & 15)) << ((row) << 2)));
    }
    backtrack(state, filled | (1LL << (row)));
  }
  state[row] = oldState;
  for (int i = 0, _n = (numRow); i < _n; i++)
    state[i] = (((state[i]) & ~(15 << ((row) << 2))) ^
                (((((oldState) >> ((i) << 2)) & 15)) << ((row) << 2)));
}
int numDigit(int x) { return x < 10 ? 1 : numDigit(x / 10) + 1; }
int solve(int x) {
  int numRow = numDigit(x);
  int code = toHexa(x, numRow);
  vector<int> state(numRow, 0);
  for (int i = 0, _n = (numRow); i < _n; i++)
    for (int j = 0, _n = (numRow); j < _n; j++)
      state[i] = (((state[i]) & ~(15 << ((j) << 2))) ^ ((10) << ((j) << 2)));
  for (int i = 0, _n = (numRow); i < _n; i++) {
    state[0] = (((state[0]) & ~(15 << ((i) << 2))) ^
                (((((code) >> ((i) << 2)) & 15)) << ((i) << 2)));
    state[i] = (((state[i]) & ~(15 << ((0) << 2))) ^
                (((((code) >> ((i) << 2)) & 15)) << ((0) << 2)));
  }
  res = 0;
  backtrack(state, (1LL << (0)));
  return res;
}
int main(void) {
  prepare();
  int t;
  scanf("%d", &t);
  for (int love = 0, _n = (t); love < _n; love++) {
    int x;
    scanf("%d", &x);
    printf("%d\n", solve(x));
  }
  return 0;
}
