#include <bits/stdc++.h>
using namespace std;
bool prime[100100];
int ord;
char num[8][8];
int ct[200100][7];
void insert(int val) {
  char buff[10];
  sprintf(buff, "%.6d", val);
  int lv = strlen(buff);
  for (int i = 0; i < 6; i++) {
    int o = buff[6 - i - 1];
    buff[6 - i - 1] = '1';
    ct[atoi(buff)][i]++;
    buff[6 - i - 1] = o;
  }
}
void calcP() {
  memset(prime, true, sizeof(prime));
  for (int i = 2; i < 100100; i++) {
    if (prime[i]) {
      insert(i);
      for (int j = 2 * i; j < 100100; j += i) {
        prime[j] = false;
      }
    }
  }
  prime[0] = prime[1] = false;
}
void reset(int v) {
  ord = 0;
  while (v != 0) {
    v /= 10;
    ord++;
  }
  for (int i = 0; i < 8; i++) {
    for (int j = 0; j < 8; j++) {
      num[i][j] = '0';
    }
  }
}
inline int pow10(int ind) {
  int ret = 1;
  for (int i = 0; i < ind; i++) {
    ret *= 10;
  }
  return ret;
}
int multi = 1;
long long out = 0;
void generate(int h) {
  if (h >= ord) {
    out += multi;
    return;
  } else {
    int val = atoi(num[h]);
    int lim = pow10(ord - h - 1);
    for (int i = 0; i < lim; i++) {
      int o = i;
      if (ct[val + i][ord - h - 1]) {
        for (int j = ord - 1; j > h; j--) {
          num[j][h] = '0' + o % 10;
          o /= 10;
        }
        multi *= ct[val + i][ord - h - 1];
        generate(h + 1);
        multi /= ct[val + i][ord - h - 1];
      }
    }
  }
}
int main() {
  calcP();
  int N;
  scanf("%d", &N);
  for (int i = 0; i < N; i++) {
    int pi;
    scanf("%d", &pi);
    reset(pi);
    sprintf(num[0], "%d", pi);
    for (int i = 0; i < ord; i++) {
      num[i][0] = num[0][i];
      num[i][ord] = '\0';
      num[i][i] = '1';
    }
    out = 0;
    generate(1);
    cout << out << endl;
  }
  return 0;
}
