#include <bits/stdc++.h>
using namespace std;
const int maxn = 101000;
const int xp[10] = {1, 10, 100, 1000, 10000, 100000, 1000000};
int prime[maxn];
vector<int> vv[5][maxn];
int get_len(int x) {
  int ans = 0;
  while (x) {
    x /= 10;
    ans++;
  }
  return ans;
}
void init() {
  for (int i = 2; i < 100000; i++)
    if (prime[i] == 0) {
      for (int j = 2; i * j < 100000; j++) prime[i * j] = 1;
      int tmp = i;
      tmp /= 10;
      for (int j = 1; j <= 4; j++) {
        vv[j][tmp].push_back(i);
        tmp /= 10;
      }
    }
}
int mm[6][6];
int siz, ans;
void dfs(int x) {
  if (x >= siz) {
    ans++;
    return;
  }
  int qian = 0;
  for (int i = 0; i < x; i++) qian = qian * 10 + mm[x][i];
  int num = vv[siz - x][qian].size();
  for (int i = 0; i < num; i++) {
    int tmp = vv[siz - x][qian][i];
    for (int j = siz - 1; j >= x; j--) {
      mm[j][x] = tmp % 10;
      tmp /= 10;
    }
    dfs(x + 1);
  }
}
int main() {
  int T;
  init();
  scanf("%d", &T);
  while (T--) {
    int x, y;
    scanf("%d", &x);
    siz = get_len(x);
    ans = 0;
    for (int i = siz - 1; i >= 0; i--) {
      mm[i][0] = x % 10;
      x /= 10;
    }
    dfs(1);
    printf("%d\n", ans);
  }
  return 0;
}
