#include <bits/stdc++.h>
using namespace std;
const int N = 101010;
int dp[10][N];
int b[6];
int prim[N];
int g[10];
int ans;
int n;
void dfs(int r, int c) {
  if (r == n) {
    int num = 1;
    for (int i = 0; i < n - 1; i++) num *= dp[i][g[n - 1 - i]];
    ans += num;
    return;
  }
  if (c == n) {
    dfs(r + 1, r + 2);
    return;
  }
  for (int i = 0; i < 10; i++) {
    g[r] += i * b[n - c - 1];
    g[c] += i * b[n - r - 1];
    dfs(r, c + 1);
    g[r] -= i * b[n - c - 1];
    g[c] -= i * b[n - r - 1];
  }
}
int main() {
  int i, j;
  b[0] = 1;
  for (i = 1; i < 6; i++) b[i] = b[i - 1] * 10;
  prim[1] = 1;
  for (i = 2; i < 400; i++) {
    if (!prim[i])
      for (j = i * i; j < N; j += i) prim[j] = 1;
  }
  for (i = 2; i < N; i++)
    if (!prim[i])
      for (j = 0; j < 5; j++) dp[j][i / b[j + 1] * b[j + 1] + i % b[j]]++;
  char s[10];
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%s", s);
    n = strlen(s);
    for (i = 1; i < n; i++) {
      g[i] = (s[i] - '0') * b[n - 1];
    }
    ans = 0;
    dfs(1, 2);
    printf("%d\n", ans);
  }
}
