#include <bits/stdc++.h>
using namespace std;
bool isp(int n) {
  if (n <= 1) return false;
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0) return false;
  return true;
}
int num[6][100000];
long long ans;
void dfs(vector<string> &vs, int r, int c, long long mul) {
  if (mul == 0) return;
  if (r >= (int)vs.size()) {
    ans += mul;
    return;
  }
  if (c >= (int)vs[0].size()) {
    int tmp = 0;
    for (int j = 0; j < (int)vs[r].size(); j++) {
      tmp *= 10;
      if (j != r) tmp += vs[r][j] - '0';
    }
    dfs(vs, r + 1, r + 2, mul * num[(int)vs.size() - 1 - r][tmp]);
    return;
  }
  for (int k = ('0'); k < ('9' + 1); k++) {
    vs[r][c] = vs[c][r] = k;
    dfs(vs, r, c + 1, mul);
  }
}
int main() {
  for (int i = (2); i < (100000); i++)
    if (isp(i)) {
      int b = 1;
      for (int j = (0); j < (5); j++) {
        int tmp = (i % (10 * b)) / b;
        tmp = i - tmp * b;
        num[j][tmp]++;
        b *= 10;
      }
    }
  int cas;
  cin >> cas;
  while (cas--) {
    string s;
    cin >> s;
    vector<string> vs((int)s.size(), s);
    for (int j = 0; j < (int)s.size(); j++) vs[j][0] = vs[0][j];
    ans = 0;
    dfs(vs, 1, 2, 1);
    cout << ans << '\n';
  }
}
