#include <bits/stdc++.h>
char mask[100005];
int idx[100005];
int primes[10000], nprimes = 0;
int dpow[] = {1, 10, 100, 1000, 10000, 100000, 1000000};
int n, len, result;
char strnum[10];
int prefs[5], trace[5];
int possible[5][100000];
void sieve() {
  int i, j;
  memset(mask, 1, sizeof(mask));
  mask[0] = 0;
  mask[1] = 0;
  for (i = 2; i < 100000; i++) {
    while (mask[i] == 0) {
      i++;
    }
    idx[i] = nprimes;
    primes[nprimes++] = i;
    for (j = i * 2; j < 100000; j += i) {
      mask[j] = 0;
    }
  }
}
int digitcount(int num, int off) {
  int i, ret = 0;
  if (possible[off][num] > -1) {
    return possible[off][num];
  }
  for (i = 0; i < 10; i++) {
    ret += mask[num + i * dpow[len - off - 1]];
  }
  possible[off][num] = ret;
  return ret;
}
void count(int off) {
  int pref = 0, lim;
  int i, j, ret;
  int backup[5];
  if (off + 1 == len) {
    trace[len - 1] = prefs[len - 1];
    ret = 1;
    for (i = 1; i < len; i++) {
      ret *= digitcount(trace[i], i);
    }
    result += ret;
    return;
  }
  memcpy(backup, prefs, sizeof(prefs));
  pref = prefs[off];
  lim = dpow[len - off - 1] + pref;
  for (i = pref; i < lim; i++) {
    if (digitcount(i, off) == 0) {
      continue;
    }
    for (j = off + 1; j < len; j++) {
      prefs[j] = backup[j] +
                 (i % dpow[len - j] / dpow[len - j - 1]) * dpow[len - off - 1];
    }
    trace[off] = i;
    count(off + 1);
  }
}
int main() {
  int num, i;
  sieve();
  scanf("%d", &n);
  while (n--) {
    result = 0;
    memset(possible, -1, sizeof(possible));
    scanf("%d", &num);
    sprintf(strnum, "%d", num);
    trace[0] = num;
    len = strlen(strnum);
    for (i = 0; i < len; i++) {
      prefs[i] = (strnum[i] - '0') * dpow[len - 1];
    }
    count(1);
    printf("%d\n", result);
  }
  return 0;
}
