#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
const int ten[] = {1, 10, 100, 1000, 10000, 100000};
int pc, lc, ans, d[6];
int pri[N], nc[6][N];
bool isp[N];
int len(int x) {
  int ret = 0;
  while (x) {
    ++ret;
    x /= 10;
  }
  return ret;
}
void dfs(int x, int n, int t) {
  if (x == n) {
    ans += t * nc[0][d[n] * 10];
  } else {
    int y = n - x;
    for (int i = 0; i < ten[y]; ++i)
      if (nc[y][d[x] * ten[y + 1] + i] != 0) {
        for (int j = x + 1; j <= n; ++j) {
          d[j] = d[j] * 10 + i / ten[n - j] % 10;
        }
        dfs(x + 1, n, t * nc[y][d[x] * ten[y + 1] + i]);
        for (int j = x + 1; j <= n; ++j) {
          d[j] /= 10;
        }
      }
  }
}
int cut(int x, int y) {
  int t = ten[y];
  return x - x / t % 10 * t;
}
int main() {
  memset(nc, 0, sizeof(nc));
  memset(isp, 1, sizeof(isp));
  pc = 0;
  for (int i = 2; i < N; ++i) {
    if (isp[i]) {
      pri[pc++] = i;
      for (int j = 0; j < 5; ++j) {
        nc[j][cut(i, j)]++;
      }
    }
    for (int j = 0; j < pc && (long long)pri[j] * i < N; ++j) {
      isp[pri[j] * i] = false;
      if (i % pri[j] == 0) {
        break;
      }
    }
  }
  int T;
  scanf("%d\n", &T);
  while (T--) {
    int n, l;
    scanf("%d", &n);
    l = len(n);
    for (int i = 0; i < l; ++i) {
      d[l - i] = n / ten[i] % 10;
    }
    ans = 0;
    dfs(2, l, 1);
    printf("%d\n", ans);
  }
}
