#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
bool flag[maxn];
int phi[maxn];
vector<int> prime;
vector<int> fin[6][maxn];
int a[10][10], num;
void get_prime_phi() {
  phi[1] = 1;
  for (int i = 2; i < 1e5; i++) {
    if (!flag[i]) {
      prime.push_back(i);
      phi[i] = i - 1;
    }
    int top = prime.size();
    for (int j = 0; j < top && i * prime[j] < 1e5; j++) {
      flag[i * prime[j]] = 1;
      if (i % prime[j])
        phi[i * prime[j]] = phi[i] * (prime[j] - 1);
      else {
        phi[i * prime[j]] = phi[i] * prime[j];
        break;
      }
    }
  }
}
void init() {
  int si = prime.size();
  for (int i = 0; i < si; i++) {
    int x = prime[i];
    for (int j = 1; j <= 5; j++) {
      fin[j][x / 10].push_back(prime[i]);
      x /= 10;
    }
  }
}
int dfs(int x) {
  int ans = 0;
  int tem = 0, tt = num - x;
  for (int i = 0; i < x; i++) tem = tem * 10 + a[x][i];
  int si = fin[tt][tem].size();
  if (x == num - 1) return si;
  for (int i = 0; i < si; i++) {
    int xx = fin[tt][tem][i];
    for (int j = num - 1; j >= x; j--) {
      a[x][j] = xx % 10;
      xx /= 10;
    }
    for (int j = x + 1; j < num; j++) a[j][x] = a[x][j];
    ans += dfs(x + 1);
  }
  return ans;
}
int main() {
  get_prime_phi();
  init();
  int cas, n;
  cin >> cas;
  while (cas--) {
    memset(a, 0, sizeof(a));
    scanf("%d", &n);
    int x = n;
    num = 0;
    while (x) {
      num++;
      x /= 10;
    }
    x = n;
    for (int i = 0; i < num; i++) {
      a[0][num - 1 - i] = a[num - 1 - i][0] = x % 10;
      x /= 10;
    }
    printf("%d\n", dfs(1));
  }
}
