#include <bits/stdc++.h>
using namespace std;
const int maxn = (int)1e5;
int pr[maxn];
int cnt[6][6][200000];
void precalc() {
  for (int i = 2; i * i <= maxn; i++)
    if (pr[i] == 0) {
      for (int j = i * i; j <= maxn; j += i) pr[j] = i;
    }
  for (int len = 1; len <= 5; len++) {
    int fin = 1;
    for (int j = 0; j < len; j++) fin *= 10;
    for (int mask = 2; mask < fin; mask++)
      if (pr[mask] == 0) {
        int rest = 0;
        int st = 1;
        int x = mask;
        for (int pos = len; pos >= 1; pos--) {
          cnt[len][pos][(x / 10) * st + rest]++;
          rest = (x % 10) * st + rest;
          x /= 10;
          st *= 10;
        }
      }
  }
}
int x[6];
int y[6];
int ret = 0;
int st[6] = {1, 10, 100, 1000, 10000, 100000};
int n = 0;
void rec(int pos) {
  if (pos == n) {
    int tmp = 1;
    for (int i = 2; i <= n; i++) tmp *= cnt[n][i][x[i] * st[n - i] + y[i]];
    ret += tmp;
    return;
  }
  int fi = 1;
  for (int j = pos + 1; j <= n; j++) fi *= 10;
  for (int mask = 1; mask < fi; mask++) {
    int xx = mask;
    y[pos] = xx;
    for (int j = n; j > pos; j--) {
      x[j] += (xx % 10) * st[j - pos - 1];
      xx /= 10;
    }
    rec(pos + 1);
    xx = mask;
    for (int j = n; j > pos; j--) {
      x[j] -= (xx % 10) * st[j - pos - 1];
      xx /= 10;
    }
  }
}
int ans(int xx) {
  n = 0;
  vector<int> dig;
  dig.clear();
  while (xx > 0) {
    n++;
    dig.push_back(xx % 10);
    xx /= 10;
  }
  for (int i = 0; i <= n; i++) {
    x[i] = y[i] = 0;
  }
  for (int i = 0; i < n; i++) x[n - i] += dig[i] * st[n - i - 2];
  ret = 0;
  rec(2);
  return ret;
}
int main() {
  int test = 0;
  cin >> test;
  precalc();
  while (test--) {
    int x = 0;
    cin >> x;
    cout << ans(x) << endl;
  }
}
