#include <bits/stdc++.h>
using namespace std;
int T, N, ans;
vector<int> P[10000][6];
int a[6], alen[6];
bool num[100000 + 5];
inline int getLen(int x) {
  int res = 0;
  while (x) {
    res++;
    x /= 10;
  }
  return res;
}
void dfs(int now) {
  if (now == N + 1) {
    ans++;
    return;
  }
  int len = alen[now] + N - now + 1, pre = a[now], sz = P[pre][len].size();
  for (int i = 0; i < sz; ++i) {
    int x = P[pre][len][i];
    for (int k = N; k > now; --k) {
      if (a[k])
        alen[k]++;
      else
        alen[k] = (x % 10 > 0);
      a[k] = a[k] * 10 + x % 10;
      x /= 10;
    }
    dfs(now + 1);
    for (int k = N; k > now; --k) {
      if (a[k]) alen[k]--;
      a[k] /= 10;
    }
  }
}
int main() {
  memset(num, true, sizeof(num));
  for (int i = 2; i * i <= 99999; ++i)
    if (num[i]) {
      for (int j = i * i; j <= 99999; j += i) num[j] = false;
    }
  for (int i = 2; i <= 99999; ++i)
    if (num[i]) {
      int len = getLen(i);
      for (int k = 10; k <= 10000; k *= 10) {
        P[i / k][len].push_back(i);
        if (i / k == 0) break;
      }
      for (int k = len + 1; k < 5; ++k) P[0][k].push_back(i);
    }
  scanf("%d", &T);
  int x;
  while (T--) {
    scanf("%d", &x);
    ans = 0;
    N = getLen(x);
    for (int i = N; i >= 2; --i) {
      a[i] = x % 10;
      if (a[i])
        alen[i] = 1;
      else
        alen[i] = 0;
      x /= 10;
    }
    dfs(2);
    cout << ans << endl;
  }
  return 0;
}
