#include <bits/stdc++.h>
using namespace std;
void ASS(bool b) {
  if (!b) {
    ++*(int*)0;
  }
}
#pragma comment(linker, "/STACK:106777216")
vector<int> p;
vector<char> IsPrime;
vector<int> pm[10][10000];
int n;
int pw10[8];
int a[8][8];
int ans = 0;
void rec(int g) {
  if (g == n) {
    ans++;
    return;
  }
  int m = 0;
  for (int i = 0; i < (int)(g); i++) m = m * 10 + a[g][i];
  const vector<int>& v = pm[g][m];
  for (int i = 0; i < (int)(v.size()); i++) {
    int x = v[i];
    for (int j = n - 1; j >= g; j--) {
      a[g][j] = a[j][g] = x % 10;
      x /= 10;
    }
    rec(g + 1);
  }
}
void Solve(int x) {
  n = 0;
  while (x) {
    a[0][n] = x % 10;
    x /= 10;
    n++;
  }
  reverse(a[0], a[0] + n);
  for (int i = 0; i < (int)(n); i++) a[i][0] = a[0][i];
  for (int i = 0; i < (int)(n + 1); i++)
    for (int j = 0; j < (int)(10000); j++) pm[i][j].clear();
  for (int k = 1; k < n; k++) {
    for (int i = 0; i < (int)(p.size()); i++) {
      if (p[i] >= pw10[n]) break;
      x = p[i];
      x /= pw10[n - k];
      pm[k][x].push_back(p[i]);
    }
  }
  ans = 0;
  rec(1);
  cout << ans << endl;
}
int main() {
  vector<char>& a = IsPrime;
  a.assign(100000, 1);
  for (int i = 2; i < (int)a.size(); i++)
    if (a[i]) {
      p.push_back(i);
      for (int j = i * 2; j < (int)a.size(); j += i) a[j] = 0;
    }
  pw10[0] = 1;
  for (int i = 0; i < (int)(7); i++) pw10[i + 1] = pw10[i] * 10;
  int t;
  cin >> t;
  for (int i = 0; i < (int)(t); i++) {
    int x;
    cin >> x;
    Solve(x);
  }
  return 0;
}
