#include <bits/stdc++.h>
using namespace std;
int n, now, p[20000], p_, g[10], ans;
int xx[10];
int tmp[10000];
int yoo[2][10000][10], f[1000][1000];
void dfs(int k) {
  int tmp = 0;
  for (int i = 1; i < k; ++i) tmp = tmp * 10 + xx[i] / g[k + 1] % 10;
  if (k == n) {
    ans += ::tmp[tmp];
    return;
  }
  for (int v = yoo[0][tmp][n - k + 1]; v <= yoo[1][tmp][n - k + 1]; v++) {
    xx[k] = p[v];
    dfs(k + 1);
  }
}
int dfss(int k) {
  int tmp = 0;
  for (int i = 1; i < k; ++i) tmp = tmp * 10 + xx[i] / g[k + 1] % 10;
  if (k == n - 1) {
    int ppp = 0;
    for (int i = 1; i < k; ++i) ppp = ppp * 10 + xx[i] / g[k + 2] % 10;
    if (f[tmp][ppp] != -1) {
      ans += f[tmp][ppp];
      return 0;
    }
    f[tmp][ppp] = 0;
    for (int v = yoo[0][tmp][n - k + 1]; v <= yoo[1][tmp][n - k + 1]; v++) {
      xx[k] = p[v];
      f[tmp][ppp] += dfss(k + 1);
    }
    return 0;
  }
  if (k == n) {
    ans += ::tmp[tmp];
    return ::tmp[tmp];
  }
  for (int v = yoo[0][tmp][n - k + 1]; v <= yoo[1][tmp][n - k + 1]; v++) {
    xx[k] = p[v];
    dfss(k + 1);
  }
}
int main() {
  int test;
  cin >> test;
  for (int i = 2; i <= 99999; ++i) {
    bool can = 1;
    for (int j = 0; j < p_; ++j)
      if (i % p[j] == 0) {
        can = 0;
        break;
      }
    if (can) p[p_++] = i;
  }
  g[0] = 100000;
  g[1] = 10000;
  g[2] = 1000;
  g[3] = 100;
  g[4] = 10;
  g[5] = 1;
  memset(yoo[1], -1, sizeof yoo[1]);
  memset(yoo[0], 63, sizeof yoo[0]);
  memset(f, -1, sizeof f);
  for (int i = 0; i < p_; ++i)
    for (int j = 0; j < 5; ++j)
      if (4 == j)
        tmp[p[i] / g[j]]++;
      else
        yoo[0][p[i] / g[j + 1]][4 - j] = min(yoo[0][p[i] / g[j + 1]][4 - j], i),
                                    yoo[1][p[i] / g[j + 1]][4 - j] =
                                        max(yoo[1][p[i] / g[j + 1]][4 - j], i);
  for (; test--;) {
    ans = 0;
    cin >> now;
    ans = 0;
    n = 0;
    for (int i = now; i; i /= 10) n++;
    g[n + 1] = 1;
    for (int i = 0; i < n; ++i) g[n - i] = g[n - i + 1] * 10;
    xx[1] = now;
    if (n < 5)
      dfs(2);
    else
      dfss(2);
    cout << ans << endl;
  }
  return 0;
}
