#include <bits/stdc++.h>
using namespace std;
int p[10000], pp;
int a[10][100010];
int t, ans, m[10];
int aa[100010];
void init() {
  pp = 1;
  p[1] = 2;
  for (int i = 3; i < 100004; i++) {
    bool b = true;
    for (int j = 1; j <= pp && p[j] * p[j] <= i && b; j++)
      if (i % p[j] == 0) b = false;
    if (b) {
      pp++;
      p[pp] = i;
    }
  }
  for (int i = 1, j = 10000; i <= 4; i++, j /= 10) {
    a[i][0] = 1;
    for (int k = 1; k < pp; k++)
      for (int l = p[k] / j + 1; l <= p[k + 1] / j; l++) a[i][l] = k + 1;
  }
}
void dfs(int k) {
  if (k == 6) ans++;
  for (int i = a[k - 1][m[k]]; i < a[k - 1][m[k] + 1]; i++) {
    int x = p[i];
    for (int l = 5; l >= k; l--) {
      m[l] = m[l] * 10 + x % 10;
      x /= 10;
    }
    dfs(k + 1);
    for (int l = 5; l >= k; l--) m[l] /= 10;
  }
}
int main() {
  init();
  memset(aa, 0, sizeof(aa));
  scanf("%d", &t);
  while (t--) {
    int x, k = 5;
    scanf("%d", &x);
    if (aa[x] > 0) {
      printf("%d\n", aa[x]);
      continue;
    }
    int xx = x;
    memset(m, 0, sizeof(m));
    while (x) {
      m[k] = x % 10;
      x /= 10;
      k--;
    }
    ans = 0;
    dfs(k + 2);
    printf("%d\n", ans);
    aa[xx] = ans;
  }
  return 0;
}
