#include <bits/stdc++.h>
using namespace std;
template <class T>
T abs(T x) {
  return x > 0 ? x : (-x);
}
template <class T>
T sqr(T x) {
  return x * x;
}
vector<int> p[7][100 * 1000];
bool isPrime(int x) {
  for (int i = 2; i * i <= x; ++i)
    if (x % i == 0) return false;
  return true;
}
int a[10];
int l;
int dfs(int x) {
  if (x >= l) return 1;
  int s = a[x], h = l - x;
  int res = 0;
  if (x == l - 1)
    res += ((int)(p[h][s]).size());
  else {
    for (int i = 0; i < ((int)(p[h][s]).size()); ++i) {
      int y = p[h][s][i];
      int t = l - 1;
      while (t >= x) {
        a[t] = a[t] * 10 + y % 10;
        y /= 10;
        --t;
      }
      res += dfs(x + 1);
      for (int j = x; j < l; ++j) a[j] /= 10;
    }
  }
  return res;
}
int main() {
  for (int i = 2; i < 100 * 1000; ++i)
    if (isPrime(i)) {
      int x = i;
      int l = 0;
      while (x) {
        p[l][x].push_back(i);
        x /= 10;
        ++l;
      }
      for (int j = l; j < 7; ++j) p[j][0].push_back(i);
    }
  int nc;
  cin >> nc;
  for (int it = 0; it < nc; ++it) {
    memset(a, 0, sizeof(a));
    int x;
    cin >> x;
    l = 0;
    vector<int> v;
    while (x) ++l, v.push_back(x % 10), x /= 10;
    for (int i = 1; i < l; ++i) a[i - 1] = v[((int)(v).size()) - i - 1];
    --l;
    time_t st = clock();
    cout << dfs(0) << "\n";
    time_t t = clock() - st;
    if (t > CLOCKS_PER_SEC * 0.1) cerr << "AAA\n";
  }
  return 0;
}
