#include <bits/stdc++.h>
using namespace std;
int p[200000];
int a[10][10];
vector<int> v[5][20000];
int n;
int rec(int i) {
  int x = 0, ans = 0, j, z, k;
  for (j = 0; j < i; j++) x = x * 10 + a[i][j];
  if (i == n - 1) return v[1][x].size();
  for (j = 0; j < v[n - i][x].size(); j++) {
    z = v[n - i][x][j];
    for (k = n - 1; k > i; k--) {
      a[i][k] = a[k][i] = z % 10;
      z /= 10;
    }
    ans += rec(i + 1);
  }
  return ans;
}
int T, i, j, x;
char s[10];
int main() {
  for (i = 2; i * i < 100000; i++)
    if (!p[i])
      for (j = i * i; j < 100000; j += i) p[j] = 1;
  for (i = 2; i < 100000; i++)
    if (!p[i]) {
      x = i / 10;
      for (j = 1; j < 5; j++) {
        v[j][x].push_back(i);
        x /= 10;
      }
    }
  scanf("%d", &T);
  while (T--) {
    scanf("%s", &s);
    for (i = 0; s[i]; i++) a[0][i] = a[i][0] = s[i] - '0';
    n = i;
    printf("%d\n", rec(1));
  }
  return 0;
}
