#include <bits/stdc++.h>
using namespace std;
int ccount[1000000 + 10];
bitset<1000000 + 100> v;
unsigned long int N;
vector<int> primes;
int cc = 0;
int primeSize;
void generatePrimes() {
  N = 1000000 + 2;
  cc = 0;
  v.set(1);
  unsigned long int i, j;
  for (i = 2; i < N + 1; i++) {
    if (!v[(int)i]) {
      for (j = i * i; j < N + 1; j += i) {
        v.set(j);
      }
      primes.push_back(i);
      ccount[(int)i] = cc;
      cc++;
    }
  }
  primeSize = cc;
}
bool isPrime(int n) { return !v[n]; }
char a[1000][1000];
int l;
int preCalc[1000000 + 1000];
int go(int level) {
  if (level == l) return 1;
  int ten = 1;
  for (int i = 0; i < l - 1; i++) ten *= 10;
  int val = 0;
  for (int i = 0; i < level; i++) {
    val += ((a[level][i] - '0') * ten);
    ten /= 10;
  }
  int x = preCalc[val];
  int target = 1;
  for (int i = 0; i < l - level; i++) target *= 10;
  target += val;
  int ans = 0;
  while (x < primeSize && primes[x] < target) {
    int m = primes[x];
    for (int i = l - 1; i >= level; i--) {
      a[i][level] = a[level][i] = (char)((m % 10) + '0');
      m /= 10;
    }
    ans += go(level + 1);
    x++;
  }
  return ans;
}
int ans[1000000 + 100];
int main() {
  int t;
  scanf("%d", &t);
  generatePrimes();
  int last = 1 << 25;
  for (int i = 1000000 - 1; i > -1; i--) {
    ans[i] = -1;
    if (isPrime(i)) {
      last = ccount[i];
    }
    preCalc[i] = last;
  }
  while (t-- > 0) {
    scanf("%s", &a[0][0]);
    l = 0;
    while (a[0][l] != '\0') l++;
    int ten = 1;
    int v = 0;
    for (int i = l - 1; i > -1; i--) {
      v += (int)(a[0][i] - '0') * ten;
      ten *= 10;
    }
    for (int i = 0; i < l; i++) a[i][0] = a[0][i];
    if (ans[v] == -1) ans[v] = go(1);
    printf("%d\n", ans[v]);
  }
}
