#include <bits/stdc++.h>
using namespace std;
bool prime[100000];
int s[10];
int ten[10] = {1, 10, 100, 1000, 10000, 100000};
int res;
int tenDiv[100000];
int tenMod[100000];
int tenMul[100000];
vector<int> ending2[100000];
vector<int> ending3[100000];
void init() {
  memset(prime, true, sizeof prime);
  prime[0] = false;
  prime[1] = false;
  for (int i = 0; i < 100000; i++) {
    tenDiv[i] = i / 10;
    tenMod[i] = i % 10;
    tenMul[i] = i * 10;
  }
  for (int i = 2; i < 100000; i++) {
    if (!prime[i]) continue;
    for (int j = 2 * i; j < 100000; j += i) {
      prime[j] = false;
    }
  }
  for (int i = 0; i < 1000; i++) {
    for (int j = 0; j < 100; j++) {
      if (prime[i * 100 + j]) {
        ending3[i].push_back(j);
      }
      if (prime[j * 1000 + i]) {
        ending2[j].push_back(i);
      }
    }
  }
}
int a[10];
void rec(int cur, int n) {
  if (cur == n) {
    res++;
    return;
  }
  int nu = s[cur - 1];
  for (int i = n - 1; i >= cur; i--) {
    a[i] = tenMul[a[i]] + tenMod[nu];
    nu = tenDiv[nu];
  }
  int k = a[cur];
  int T = ten[n - cur];
  int kT = k * T;
  if (n == 5 && cur == 2) {
    for (int i = 0; i < ending2[k].size(); i++) {
      int number = ending2[k][i];
      int num = number + kT;
      if (!prime[num]) continue;
      s[cur] = num;
      rec(cur + 1, n);
    }
  } else if (n == 5 && cur == 3) {
    for (int i = 0; i < ending3[k].size(); i++) {
      int number = ending3[k][i];
      int num = number + kT;
      if (!prime[num]) continue;
      s[cur] = num;
      rec(cur + 1, n);
    }
  } else {
    for (int number = 0; number < T; number++) {
      int num = number + kT;
      if (!prime[num]) continue;
      s[cur] = num;
      rec(cur + 1, n);
    }
  }
  for (int i = n - 1; i >= cur; i--) {
    a[i] = tenDiv[a[i]];
  }
}
int getLen(int num) {
  int res = 0;
  while (num > 0) {
    res++;
    num /= 10;
  }
  return res;
}
void calc() {
  a[0] = s[0];
  int n = getLen(s[0]);
  rec(1, n);
}
int main() {
  init();
  int n;
  scanf("%d", &n);
  int M = 0;
  for (int i = 0; i < n; i++) {
    memset(s, 0, sizeof s);
    memset(a, 0, sizeof a);
    scanf("%d", &s[0]);
    res = 0;
    calc();
    printf("%d\n", res);
  }
  return 0;
}
