#include <bits/stdc++.h>
using namespace std;
const int MAX = 100000;
int w[MAX];
vector<int> prime[MAX][6];
int cnt;
int matrix[5][5], W, T, P, ans;
inline void dfs(int n) {
  if (n == W) {
    ++ans;
    return;
  }
  int mask = 0;
  for (int i = 0; i < n; ++i) mask = mask * 10 + matrix[n][i];
  int nw = W;
  for (int i = 0; i < n && matrix[n][i] == 0; ++i, --nw)
    ;
  if (mask) {
    for (int i = 0; i < prime[mask][nw].size(); ++i) {
      int t = prime[mask][nw][i];
      for (int j = W - 1; j >= n; --j) matrix[n][j] = t % 10, t /= 10;
      for (int j = n + 1; j < W; ++j) matrix[j][n] = matrix[n][j];
      dfs(n + 1);
      for (int j = n; j < W; ++j) matrix[n][j] = matrix[j][n] = -1;
    }
  } else {
    for (int j = 0; j <= nw; ++j)
      for (int i = 0; i < prime[0][j].size(); ++i) {
        int t = prime[0][j][i];
        for (int j = W - 1; j >= n; --j) matrix[n][j] = t % 10, t /= 10;
        for (int j = n + 1; j < W; ++j) matrix[j][n] = matrix[n][j];
        dfs(n + 1);
        for (int j = n; j < W; ++j) matrix[n][j] = matrix[j][n] = -1;
      }
  }
}
inline bool judge(int n) {
  for (int i = 2; i * i <= n; ++i)
    if (n % i == 0) return false;
  return n > 1;
}
int main() {
  w[0] = 0;
  for (int i = 1; i < MAX; ++i) w[i] = w[i / 10] + 1;
  for (int i = 0; i < MAX; ++i)
    for (int j = 1; j <= 5; ++j) prime[i][j].clear();
  for (int i = 2; i < MAX; ++i)
    if (judge(i)) {
      int t = i;
      prime[0][w[i]].push_back(i);
      while (t) prime[t][w[i]].push_back(i), t /= 10;
    }
  scanf("%d", &T);
  while (T--) {
    scanf("%d", &P);
    W = w[P];
    memset(matrix, -1, sizeof(matrix));
    int t = P;
    for (int i = W - 1; i >= 0; --i) matrix[0][i] = t % 10, t /= 10;
    for (int i = 1; i < W; ++i) matrix[i][0] = matrix[0][i];
    ans = 0;
    dfs(1);
    printf("%d\n", ans);
  }
  return 0;
}
