#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int num;
int minp[MAXN + 1], p[MAXN + 1];
int prime(int n = MAXN) {
  num = 0;
  memset(minp, 0, sizeof(minp));
  for (int i = 2; i <= n; ++i) {
    if (!minp[i]) p[num++] = i, minp[i] = i;
    ;
    for (int j = 0; j < num && i * p[j] <= n; ++j) {
      minp[i * p[j]] = p[j];
      if (i % p[j] == 0) break;
    }
  }
  return num;
}
int n, m, res;
int ten[10];
int cnt[10000][5];
int id[5];
void gao(int r, int c) {
  if (r == n) {
    int cur = 1;
    for (int i = 1; i < n; ++i) {
      cur *= cnt[id[i]][i];
    }
    res += cur;
  } else {
    int nr = c + 1 == r ? r + 1 : r;
    int nc = c + 1 == r ? 1 : c + 1;
    id[r] *= 10;
    id[c] *= 10;
    for (int i = 0; i < 10; ++i) {
      gao(nr, nc);
      ++id[r];
      ++id[c];
    }
    id[c] = id[c] / 10 - 1;
    id[r] = id[r] / 10 - 1;
  }
}
int main() {
  prime();
  for (int i = ten[0] = 1; i < 7; ++i) {
    ten[i] = ten[i - 1] * 10;
  }
  int T, v;
  scanf("%d", &T);
  for (int caseNum = 1; caseNum <= T; ++caseNum) {
    scanf("%d", &v);
    n = 0;
    for (n = 0, m = v; m != 0; m /= 10, ++n)
      ;
    memset(id, 0, sizeof(id));
    for (int i = 1; i < n; ++i) {
      id[i] = v / ten[n - i - 1] % 10;
    }
    memset(cnt, 0, sizeof(cnt));
    for (int i = 0; i < num && p[i] < ten[n]; ++i) {
      int d[5];
      for (int j = 0, t = p[i]; j < n; d[n - 1 - j++] = t % 10, t /= 10)
        ;
      for (int j = 1; j < n; ++j) {
        int t = 0;
        for (int k = 0; k < n; ++k) {
          if (k != j) {
            t = t * 10 + d[k];
          }
        }
        ++cnt[t][j];
      }
    }
    res = 0;
    gao(2, 1);
    printf("%d\n", res);
  }
  return 0;
}
