#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:100000000")
int fst[7][100500];
int lst[7][100500];
int a[10];
bool p[100500];
vector<int> pr;
int solve(int k, int len) {
  if (k == len) return 1;
  int i, j;
  int res = 0;
  if (fst[k][a[k]] == -1) return 0;
  for (i = fst[k][a[k]]; i <= lst[k][a[k]]; ++i) {
    int xx = pr[i];
    for (j = len - 1; j > k; --j) {
      a[j] = a[j] * 10 + xx % 10;
      xx /= 10;
    }
    res += solve(k + 1, len);
    for (j = len - 1; j > k; --j) a[j] /= 10;
  }
  return res;
}
int main() {
  int i, j;
  memset(p + 2, true, sizeof(p));
  for (i = 2; i < 100000; ++i) {
    if (!p[i]) continue;
    pr.push_back(i);
    for (j = 2 * i; j < 100000; j += i) p[j] = false;
  }
  memset(fst, 0xff, sizeof(fst));
  memset(lst, 0xff, sizeof(lst));
  for (i = 0; i < pr.size(); ++i) {
    if (fst[1][pr[i] / 10000] == -1) fst[1][pr[i] / 10000] = i;
    lst[1][pr[i] / 10000] = i;
    if (fst[2][pr[i] / 1000] == -1) fst[2][pr[i] / 1000] = i;
    lst[2][pr[i] / 1000] = i;
    if (fst[3][pr[i] / 100] == -1) fst[3][pr[i] / 100] = i;
    lst[3][pr[i] / 100] = i;
    if (fst[4][pr[i] / 10] == -1) fst[4][pr[i] / 10] = i;
    lst[4][pr[i] / 10] = i;
  }
  int t;
  scanf("%d", &t);
  for (i = 0; i < t; ++i) {
    int x;
    scanf("%d", &x);
    int xx = x;
    int len = 0;
    for (j = 0; j < 5; ++j) a[j] = 0;
    while (xx > 0) {
      a[len] = xx % 10;
      xx /= 10;
      len++;
    }
    reverse(a, a + 5);
    int ans = solve(5 - len + 1, 5);
    printf("%d\n", ans);
  }
  return 0;
}
