#include <bits/stdc++.h>
using namespace std;
int r, u[6][6], p[100100];
vector<vector<int> > v[6][6];
int len(int n) {
  int i;
  for (i = 0; n; i++, n /= 10)
    ;
  return i;
}
void upd(int n) {
  int i, j, k;
  for (i = len(n); i <= 5; i++)
    for (k = n, j = i; j; v[i][j][k].push_back(n), k /= 10, j--)
      ;
}
void rec(int i, int n) {
  int t, j, l, k;
  if (i == n)
    r++;
  else {
    for (t = 0, j = 0; j < i; t = t * 10 + u[j][i], j++)
      ;
    for (j = v[n][i][t].size(); j--; rec(i + 1, n))
      for (k = v[n][i][t][j], l = n; l >= i; l--, u[i][l] = k % 10, k /= 10)
        ;
  }
}
int main() {
  int t, n, i, j;
  for (t = 10, i = 1; i <= 5; t *= 10, i++)
    for (j = 1; j <= i; v[i][j].resize(t), j++)
      ;
  for (p[0] = 1, p[1] = 1, i = 2; i * i < 100100; i++)
    if (!p[i])
      for (j = i * i; j < 100100; p[j] = 1, j += i)
        ;
  for (i = 0; i < 100100; i++)
    if (!p[i]) upd(i);
  for (scanf("%d", &t); t--;) {
    scanf("%d", &n);
    if (!p[n]) {
      for (j = n, i = 0; j; u[0][i] = j % 10, j /= 10, i++)
        ;
      reverse(u[0], u[0] + i);
      r = 0;
      rec(1, i);
      p[n] = r;
    }
    printf("%d\n", p[n]);
  }
  return 0;
}
