#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:64000000")
using namespace std;
template <class T>
T sqr(T a) {
  return a * a;
}
int lnk[110000];
int pr[110000];
int mtx[6][6];
int prc;
int n;
int result;
void find(int k, int p) {
  int f = 0;
  for (int i = 0; i < k; i++) f = f * 10 + mtx[k][i];
  for (int i = lnk[f * p]; i < prc && pr[i] < (f + 1) * p; i++) {
    if (k == n - 1)
      result++;
    else {
      int z = pr[i];
      for (int j = n - 1; j >= k; j--) {
        mtx[k][j] = mtx[j][k] = z % 10;
        z /= 10;
      }
      find(k + 1, p / 10);
    }
  }
}
int main() {
  lnk[1] = 1;
  for (int i = 2; i <= 100000; i++)
    if (!lnk[i]) {
      pr[prc++] = i;
      for (int j = i * 2; j <= 100000; j += i) lnk[j] = 1;
    }
  int cur = prc;
  for (int i = 100000; i >= 1; i--) {
    if (!lnk[i]) cur--;
    lnk[i] = cur;
  }
  int tn;
  cin >> tn;
  for (int tc = 0; tc < tn; tc++) {
    int num;
    cin >> num;
    n = 0;
    int p = 1;
    while (p <= num) {
      n++;
      p *= 10;
    }
    for (int i = n - 1; i >= 0; i--) {
      mtx[0][i] = mtx[i][0] = num % 10;
      num /= 10;
    }
    result = 0;
    find(1, p / 10);
    cout << result << endl;
  }
  return 0;
}
