#include <bits/stdc++.h>
using namespace std;
const int Vmax = 100000;
int cntPrimes[6][6][Vmax];
char A[7][7];
void addPrime(int x) {
  for (int digits = 1; digits <= 5; ++digits) {
    for (int i = 1; i <= 5; ++i) {
      int dig[5];
      int y = x;
      for (int j = 0; j < digits; ++j) {
        dig[j] = y % 10;
        y /= 10;
      }
      dig[digits - i] = 0;
      for (int j = digits - 1; j >= 0; --j) y = 10 * y + dig[j];
      cntPrimes[digits][i][y]++;
    }
  }
}
void genPrimes(int N) {
  vector<bool> notPrime(N, false);
  for (int i = 2; i * i < N; ++i)
    if (!notPrime[i])
      for (int j = i * i; j < N; j += i) notPrime[j] = true;
  for (int i = 2; i < N; ++i)
    if (!notPrime[i]) addPrime(i);
}
int N;
int ans = 0;
void back(int row, int col) {
  if (col == N + 1) {
    row++;
    col = row + 1;
  }
  if (row >= N) {
    int add = 1;
    for (int i = 2; i <= N; ++i) {
      int x = 0;
      for (int j = 1; j <= N; ++j) x = 10 * x + A[i][j] - '0';
      add *= cntPrimes[N][i][x];
    }
    ans += add;
  } else {
    for (int i = 0; i < 10; ++i) {
      A[row][col] = A[col][row] = i + '0';
      back(row, col + 1);
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  genPrimes(100000);
  int T;
  cin >> T;
  while (T-- > 0) {
    cin >> (A[1] + 1);
    N = strlen(A[1] + 1);
    for (int i = 1; i <= N; ++i) A[i][1] = A[1][i];
    for (int i = 2; i <= N; ++i)
      for (int j = 2; j <= N; ++j) A[i][j] = '0';
    ans = 0;
    back(2, 3);
    cout << ans << '\n';
  }
}
