#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:60777216")
using namespace std;
string filename = "input";
bool is_p[100000];
vector<int> pref[6][100000];
vector<int> primes;
vector<vector<int> > mat;
int mem[1000];
int go(int row) {
  if (row == mat.size()) {
    return 1;
  }
  int tval = 0;
  if (row == 2) {
    for (int _n(mat.size()), i(2); i < _n; i++) {
      tval *= 10;
      tval += mat[i][1];
    }
    if (mem[tval] != -1) return mem[tval];
  }
  int val = 0;
  int cnt_z = 0;
  for (int _n(row), i(0); i < _n; i++) {
    val = val * 10 + mat[row][i];
    if (val == 0) ++cnt_z;
  }
  int len = 0;
  if (val == 0) {
    len = mat.size() - row + 1;
  } else {
    len = mat.size() - cnt_z;
  }
  const vector<int>& prefs = pref[len][val];
  int ret = 0;
  for (int _n(prefs.size()), i(0); i < _n; i++) {
    int p = prefs[i];
    for (int j = mat[row].size() - 1; j >= row; --j, p /= 10) {
      mat[row][j] = mat[j][row] = p % 10;
    }
    ret += go(row + 1);
  }
  if (row == 2) mem[tval] = ret;
  return ret;
}
int main() {
  memset(pref, 0, sizeof(pref));
  memset(is_p, true, sizeof(is_p));
  is_p[0] = is_p[1] = false;
  for (int i = 2; i < 100000; ++i) {
    if (is_p[i]) {
      primes.push_back(i);
      for (int j = 2; i * j < 100000; ++j) is_p[i * j] = false;
    }
  }
  for (int _n(primes.size()), i(0); i < _n; i++) {
    ostringstream ccout;
    ccout << primes[i];
    string s = ccout.str();
    int p = primes[i];
    for (int _n(6), len(s.size() + 1); len < _n; len++)
      pref[len][0].push_back(p);
    int d0 = 0;
    for (int _n(s.size()), j(0); j < _n; j++) {
      d0 *= 10;
      d0 += (s[j] - '0');
      pref[s.size()][d0].push_back(p);
    }
  }
  int T;
  scanf("%d", &T);
  for (int _n(T), test(0); test < _n; test++) {
    int p;
    scanf("%d", &p);
    mat = vector<vector<int> >(1, vector<int>());
    while (p) {
      mat[0].push_back(p % 10);
      p /= 10;
    }
    reverse((mat[0]).begin(), (mat[0]).end());
    for (int _n(mat[0].size() - 1), i(0); i < _n; i++)
      mat.push_back(vector<int>(mat[0].size(), 0));
    for (int _n(mat.size()), i(1); i < _n; i++) {
      mat[i][0] = mat[0][i];
    }
    memset(mem, -1, sizeof(mem));
    int res = go(1);
    cout << res << endl;
  }
  return 0;
}
