#include <bits/stdc++.h>
using namespace std;
struct _ {
  _() { ios_base::sync_with_stdio(0); }
} _;
template <class A, class B>
ostream &operator<<(ostream &o, pair<A, B> t) {
  o << "(" << t.first << ", " << t.second << ")";
  return o;
}
template <class T>
string tostring(T first, int len = 0, char c = '0') {
  stringstream ss;
  ss << first;
  string r = ss.str();
  if (r.length() < len) r = string(len - r.length(), c) + r;
  return r;
}
template <class T>
void PV(T a, T b, int n = 0, int w = 0, string s = " ") {
  int c = 0;
  while (a != b) {
    cout << tostring(*a++, w, ' ');
    if (a != b && (n == 0 || ++c % n))
      cout << s;
    else
      cout << endl;
  }
}
template <class T>
inline bool chmin(T &a, T b) {
  return a > b ? a = b, 1 : 0;
}
template <class T>
inline bool chmax(T &a, T b) {
  return a < b ? a = b, 1 : 0;
}
const long long linf = 0x3f3f3f3f3f3f3f3fLL;
const int inf = 0x3f3f3f3f;
const int mod = int(1e9) + 7;
const int N = 111111;
vector<int> prime;
bool isp[N];
vector<int> oddPrime;
void generatePrime(int n = 1000000) {
  memset(isp, 1, sizeof(isp));
  ;
  isp[0] = isp[1] = 0;
  for (int i = 2; i <= n; i++) {
    if (!isp[i]) continue;
    prime.push_back(i);
    for (int j = i + i; j <= n; j += i) {
      isp[j] = 0;
    }
  }
}
int cnt[10000];
long long cc;
inline int isPrime(int *a, int n) {
  int r = 0;
  for (int i = 0; i < n; i++) r = 10 * r + a[i];
  return isp[r];
}
int D[5][5], n, res;
void dfs(int r, int c) {
  if (n <= 4 && r == n - 1) {
    res++;
    return;
  }
  if (n == 5 && r == n - 2) {
    res += cnt[D[3][0] * 1000 + D[3][1] * 100 + D[3][2] * 10 + D[3][4]];
    return;
  }
  for (int i = 0; i < 10; i++) {
    D[r][c] = D[c][r] = i;
    if (c == n - 2) {
      if (isPrime(D[r], n)) dfs(r + 1, r + 1);
    } else {
      dfs(r, c + 1);
    }
    if (D[r][n - 1] == 2) break;
  }
}
int main() {
  generatePrime(100000);
  for (int i : prime) {
    int t = i;
    int ok = 1;
    while (t > 0) {
      if (t % 10 != 2 && t % 2 == 0) ok = 0;
      t /= 10;
    }
    if (ok) oddPrime.push_back(i);
    int j = i / 100 * 10 + i % 10;
    cnt[j]++;
  }
  int T;
  cin >> T;
  while (T--) {
    int first;
    cin >> first;
    string s = tostring(first);
    n = s.length();
    res = 0;
    for (int second : oddPrime) {
      if (tostring(second).size() > n) continue;
      for (int i = 0; i < n; i++) D[0][i] = D[i][0] = s[i] - '0';
      string os = tostring(second, n);
      if (os[0] != s[n - 1]) continue;
      int ok = 1;
      for (int i = 0; i < n; i++) {
        int t = os[i] - '0';
        D[i][n - 1] = D[n - 1][i] = t;
        if (t % 2 == 0 && D[0][i] != 0) ok = 0;
      }
      if (ok) dfs(1, 1);
    }
    cout << res << endl;
  }
  cerr << "["
          "0"
          " -> "
          "clock()"
          ": "
       << 1e3 * (clock() - 0) / CLOCKS_PER_SEC << "ms]\n";
  ;
  return 0;
}
