#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 100500;
const int maxn = 10;
const int p10[] = {1, 10, 100, 1000, 10000, 100000};
const int x[] = {2, 3, 3, 4, 4, 4};
const int y[] = {1, 1, 2, 1, 2, 3};
const int stop[] = {0, 0, 0, 1, 3, 6};
int mlog(int x) {
  if (x < 100) return 2;
  if (x < 1000) return 3;
  if (x < 10000) return 4;
  return 5;
}
bool prime(int x) {
  for (int i = 2; i * i <= x; i++)
    if (x % i == 0) return false;
  return true;
}
int digit(int x, int k) {
  for (int i = 0; i < (int)(k); i++) x /= 10;
  return x % 10;
}
int d[100005][maxn];
void comp() {
  for (int i = (int)(2); i <= (int)(99999); i++)
    if (prime(i)) {
      for (int j = 0; j < (int)(5); j++)
        d[i % p10[j] + i / p10[j + 1] * p10[j]][j]++;
    }
}
int n;
int a[maxn][maxn];
int get(int lim = n) {
  int pr = 1;
  for (int i = 1; i < lim; i++) {
    int x = 0;
    for (int j = 0; j < (int)(n); j++)
      if (j != i) x = x * 10 + a[i][j];
    pr *= d[x][n - i - 1];
    if (pr == 0) break;
  }
  return pr;
}
long long go(int pos) {
  if (pos == stop[n]) return get();
  long long s = 0;
  for (int i = (int)(0); i <= (int)(9); i++) {
    if (x[pos] == n - 1 && i != 2 && i % 2 == 0) continue;
    a[x[pos]][y[pos]] = a[y[pos]][x[pos]] = i;
    s += go(pos + 1);
  }
  return s;
}
void solve() {
  int x;
  cin >> x;
  n = mlog(x);
  for (int i = 0; i < (int)(n); i++) a[i][0] = a[0][i] = digit(x, n - i - 1);
  cout << go(0) << endl;
}
int main() {
  comp();
  int t;
  cin >> t;
  for (int i = 0; i < (int)(t); i++) solve();
  return 0;
}
