#include <bits/stdc++.h>
using namespace std;
const int pp[6] = {0, 1, 10, 100, 1000, 10000};
bool pri[100000];
int psum[100000];
int x[6][6], s[6];
int ans, sum, t;
bool is_prime(int x) {
  for (int i = 2; i <= (int)(sqrt(x) + 1e-8); i++)
    if (x % i == 0) return 0;
  return 1;
}
void prep() {
  memset(pri, 0, sizeof(pri));
  memset(psum, 0, sizeof(psum));
  for (int i = 2; i <= 99999; i++)
    if (is_prime(i)) {
      pri[i] = true;
      psum[i - (i / 10 % 10) * 10]++;
    }
}
void dfs(int tx, int ty) {
  if (tx == sum) {
    ans++;
    return;
  }
  if (tx == sum - 1 && ty == 2) {
    ans += psum[s[tx]];
    return;
  }
  int tt = 0, ttt = 0;
  for (int i = 0; i <= 9; i++) {
    x[tx][ty] = i;
    x[sum - ty + 1][sum - tx + 1] = i;
    s[tx] += ttt;
    if (tx + ty != sum + 1) s[sum - ty + 1] += tt;
    if (ty == 2) {
      if (pri[s[tx]]) dfs(tx + 1, sum - tx);
    } else
      dfs(tx, ty - 1);
    s[tx] -= ttt;
    if (tx + ty != sum + 1) s[sum - ty + 1] -= tt;
    tt += pp[sum - tx + 1];
    ttt += pp[ty];
  }
}
void Dfs(int tx) {
  const int num[7] = {0, 1, 3, 5, 7, 9, 2};
  for (int i = 1; i <= 6; i++) {
    if (i == 6 && x[tx][sum] != 0) return;
    x[tx][1] = num[i];
    x[sum][sum - tx + 1] = num[i];
    s[tx] += num[i] * pp[1];
    if (tx == sum) {
      if (pri[s[tx]]) dfs(2, sum - 1);
    } else {
      s[sum] += num[i] * pp[sum - tx + 1];
      Dfs(tx + 1);
      s[sum] -= num[i] * pp[sum - tx + 1];
    }
    s[tx] -= num[i] * pp[1];
  }
}
void solve() {
  int p;
  cin >> p;
  sum = 0;
  while (p > 0) {
    x[1][++sum] = p % 10;
    p /= 10;
  }
  for (int i = 2; i <= sum; i++) x[i][sum] = x[1][sum - i + 1];
  ans = 0;
  for (int i = 2; i <= sum; i++) s[i] = x[i][sum] * pp[sum];
  Dfs(2);
  cout << ans << endl;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> t;
  prep();
  for (int i = 1; i <= t; i++) solve();
  return 0;
}
