#include <bits/stdc++.h>
using namespace std;
const int MaxN = 100500;
const int MaxP = 9632;
const int MaxK = 6;
const int MaxM = MaxP * MaxK;
bool fd[MaxN];
int p[MaxP], pn;
int mp[MaxK][MaxK];
int res[MaxN];
int N, K;
struct Node {
  int cnt;
  Node* next[10];
} memo[MaxM], *cur, *root;
Node* new_node() {
  cur->cnt = 0;
  fill(cur->next, cur->next + 10, (Node*)NULL);
  return cur++;
}
void insert(int N) {
  int d[MaxK];
  for (int i = K - 1; i >= 0; i--) {
    d[i] = N % 10;
    N /= 10;
  }
  Node* ptr = root;
  for (int i = 0; i < K; i++) {
    if (ptr->next[d[i]] == NULL) ptr->next[d[i]] = new_node();
    ptr = ptr->next[d[i]];
    ptr->cnt++;
  }
}
int getD(int N) {
  int ret = 0;
  while (N) {
    ret++;
    N /= 10;
  }
  return ret;
}
void init() {
  cur = memo;
  root = new_node();
  for (int i = 0; i < pn; i++) {
    if (getD(p[i]) > K) break;
    insert(p[i]);
  }
}
void init_p() {
  fd[0] = fd[1] = true;
  for (int i = 2; i < MaxN; i++) {
    if (!fd[i]) p[pn++] = i;
    for (int j = 0; j < pn && i * p[j] < MaxN; j++) {
      fd[i * p[j]] = true;
      if (i % p[j] == 0) break;
    }
  }
}
void getH(int* d, int N) {
  for (int i = K - 1; i >= 0; i--) {
    d[i] = N % 10;
    N /= 10;
  }
}
int ret;
void DFS(int k);
void DFS(int k, int p, Node* ptr) {
  if (k == K - 1) {
    ret += ptr->cnt;
    return;
  }
  if (p == K) {
    DFS(k + 1);
    return;
  }
  for (int i = 0; i < 10; i++) {
    if (ptr->next[i]) {
      mp[k][p] = mp[p][k] = i;
      DFS(k, p + 1, ptr->next[i]);
    }
  }
}
void DFS(int k) {
  Node* ptr = root;
  for (int i = 0; i < k; i++)
    if (ptr->next[mp[k][i]])
      ptr = ptr->next[mp[k][i]];
    else
      return;
  DFS(k, k, ptr);
}
int main() {
  int T;
  memset(res, -1, sizeof(res));
  init_p();
  scanf("%d", &T);
  while (T--) {
    scanf("%d", &N);
    K = getD(N);
    init();
    ret = 0;
    getH(mp[0], N);
    for (int i = 1; i < K; i++) mp[i][0] = mp[0][i];
    if (res[N] != -1)
      ret = res[N];
    else {
      DFS(1);
      res[N] = ret;
    }
    printf("%d\n", ret);
  }
  return 0;
}
