#include <bits/stdc++.h>
using namespace std;
bool prime[2 * 100500];
int pr[100500], prs;
int nxt[100500];
int ten[10];
int a[7][7];
vector<int> pd[100500];
int onedig[100500];
int solve(int n) {
  if (n == 1) return onedig[a[n][0]];
  int *b = a[n];
  int *aa = a[n - 1];
  int lim = nxt[(b[0] + 1) * ten[n]];
  int ans = 0;
  for (int pri = nxt[b[0] * ten[n]]; pri < lim; pri++) {
    vector<int> &v = pd[pr[pri]];
    for (int i = 0; i < (n - 1); i++) {
      aa[n - 2 - i] = b[n - 1 - i] * 10 + v[i];
    }
    ans += solve(n - 1);
  }
  return ans;
}
void solve1(int p0) {
  vector<int> d;
  while (p0 >= 10) d.push_back(p0 % 10), p0 /= 10;
  reverse(d.begin(), d.end());
  int n = ((int)((d).size()));
  for (int i = 0; i < (n); i++) a[n][i] = d[i];
  printf("%d\n", solve(n));
}
int main() {
  memset(prime, 1, sizeof prime);
  prime[0] = prime[1] = false;
  for (int i = 2; i * i <= 2 * 100500; i++)
    if (prime[i])
      for (int j = i * i; j < 2 * 100500; j += i) prime[j] = false;
  prs = 0;
  for (int i = 0; i < (100500); i++)
    if (prime[i]) pr[prs++] = i;
  nxt[0] = nxt[1] = 0;
  for (int i = 1; i < prs; i++) {
    for (int j = pr[i - 1] + 1; j <= pr[i]; j++) nxt[j] = i;
  }
  ten[0] = 1;
  for (int i = 0; i < (7); i++) ten[i + 1] = ten[i] * 10;
  for (int i = 0; i < (100500); i++)
    if (prime[i]) {
      int p = i;
      for (int _ = 0; _ < (8); _++) pd[i].push_back(p % 10), p /= 10;
    }
  for (int i = 0; i < (100500 / 10); i++) {
    for (int d = 0; d < (10); d++) onedig[i] += prime[i * 10 + d];
  }
  int __;
  scanf("%d", &__);
  for (int _ = 0; _ < (__); _++) {
    int p;
    scanf("%d", &p);
    solve1(p);
  }
  return 0;
}
