#include <bits/stdc++.h>
bool notp[100000];
int ans, val[9], p[9], n, dp[6][100000];
void dfs(int r, int c) {
  if (r == n) {
    int t = 1;
    for (int i = 1; i < n; ++i) t *= dp[n - 1 - i][val[i]];
    ans += t;
    return;
  }
  if (c == n) {
    dfs(r + 1, r + 2);
    return;
  }
  for (int i = 0; i < 10; ++i) {
    val[r] += i * p[n - 1 - c];
    val[c] += i * p[n - 1 - r];
    dfs(r, c + 1);
    val[r] -= i * p[n - 1 - c];
    val[c] -= i * p[n - 1 - r];
  }
}
int main() {
  int T;
  char s[9];
  p[0] = 1;
  for (int i = 1; i < 7; ++i) p[i] = p[i - 1] * 10;
  for (int i = 2; i < 100000; ++i)
    if (!notp[i]) {
      if (i < 316)
        for (int j = i * i; j < 100000; j += i) notp[j] = 1;
      for (int j = 0; j < 6; ++j) dp[j][i / p[j + 1] * p[j + 1] + i % p[j]]++;
    }
  while (scanf("%d", &T) != EOF) {
    while (T--) {
      scanf("%s", s);
      ans = val[0] = 0;
      for (n = 0; s[n]; ++n) val[0] = val[0] * 10 + s[n] - '0';
      for (int i = 1; i < n; ++i) val[i] = (s[i] - '0') * p[n - 1];
      dfs(1, 2);
      printf("%d\n", ans);
    }
  }
  return 0;
}
