#include <bits/stdc++.h>
using namespace std;
vector<int> Sieve(int abc) {
  vector<int> sieveans;
  abc++;
  sieveans.reserve(abc);
  for (int(i) = 0; (i) < (abc); ++(i)) sieveans.push_back(1);
  for (int i = 2; i * i < abc; i = (i == 2) ? 3 : (i + 2)) {
    for (int j = i + i; j < abc; j += i) {
      sieveans[j] = 0;
    }
  }
  sieveans[0] = sieveans[1] = 0;
  return sieveans;
}
vector<int> GetDigits(long long number) {
  if (number == 0LL) return vector<int>(0);
  vector<int> ret;
  while (number) {
    ret.push_back((int)(number % 10LL));
    number /= 10LL;
  }
  reverse(ret.begin(), ret.end());
  return ret;
}
vector<vector<int> > p1d[10][6];
vector<vector<int> > p2d[10][10][6];
vector<vector<int> > p3d[10][10][10][6];
vector<vector<int> > p4d[10][10][10][10][6];
int isprime[120000];
int box[6][6];
long long Solve(int s, int n) {
  if (s == n) return 1LL;
  vector<vector<int> >* loc;
  int w = s - 1;
  if (s == 2) {
    loc = &(p2d[box[w][0]][box[w][n - 1]][n]);
  } else if (s == 3) {
    loc = &(p3d[box[w][0]][box[w][1]][box[w][n - 1]][n]);
  } else if (s == 4) {
    return (
        (int)(p4d[box[w][0]][box[w][1]][box[w][2]][box[w][n - 1]][n]).size());
  } else {
    assert(false);
  }
  vector<vector<int> >& ref = *loc;
  long long res = 0LL;
  for (int(i) = 0; (i) < (((int)(ref).size())); ++(i)) {
    for (int(j) = 0; (j) < (n); ++(j)) box[w][j] = box[j][w] = ref[i][j];
    res += Solve(s + 1, n);
  }
  return res;
}
int main() {
  {
    vector<int> base = Sieve(120000);
    for (int(i) = 0; (i) < (120000); ++(i)) isprime[i] = base[i];
    for (int(i) = 0; (i) < (120000); ++(i))
      if (isprime[i]) {
        vector<int> d = GetDigits(i);
        for (int(i) = (2); (i) < (6); ++(i)) {
          if (((int)(d).size()) > i) continue;
          while (((int)(d).size()) < i) d.insert(d.begin(), 0);
          p1d[d[0]][i].push_back(d);
          p2d[d[0]][d.back()][i].push_back(d);
          if (i >= 3) p3d[d[0]][d[1]][d.back()][i].push_back(d);
          if (i >= 4) p4d[d[0]][d[1]][d[2]][d.back()][i].push_back(d);
        }
      }
  }
  int ntc;
  cin >> ntc;
  for (int(itc) = 0; (itc) < (ntc); ++(itc)) {
    int x;
    cin >> x;
    vector<int> d = GetDigits(x);
    if (!isprime[x]) {
      cout << 0 << endl;
      continue;
    }
    int n = ((int)(d).size());
    for (int(i) = 0; (i) < (n); ++(i)) {
      box[0][i] = box[i][0] = d[i];
    }
    long long res = 0LL;
    for (int(i) = 0; (i) < (((int)(p1d[box[n - 1][0]][n]).size())); ++(i)) {
      for (int(j) = 0; (j) < (n); ++(j))
        box[n - 1][j] = box[j][n - 1] = p1d[box[n - 1][0]][n][i][j];
      res += Solve(2, n);
    }
    cout << res << endl;
  }
}
