#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
int q, n;
bool visited[MAXN];
vector<int> prim;
map<vector<int>, int> dp;
inline int get_length(int n) {
  int ret = 0;
  while (n > 0) {
    n /= 10;
    ++ret;
  }
  return ret;
}
int dfs(vector<int> v) {
  if ((int)v.size() == 0) return 1;
  if (dp.count(v)) return dp[v];
  int ten = 1, m = (int)v.size();
  for (int i = 0; i < m; ++i) ten *= 10;
  int low = v[0] * ten, upp = (v[0] + 1) * ten;
  int it1 = lower_bound(prim.begin(), prim.end(), low) - prim.begin();
  int it2 = lower_bound(prim.begin(), prim.end(), upp) - prim.begin();
  int ret = 0;
  for (int i = it1; i < it2; ++i) {
    vector<int> tmp;
    int x = prim[i];
    for (int j = 1; j < m; ++j) tmp.push_back(v[j]);
    for (int j = m - 2; j >= 0; --j) {
      tmp[j] = tmp[j] * 10 + x % 10;
      x /= 10;
    }
    ret += dfs(tmp);
  }
  return dp[v] = ret;
}
int main() {
  for (int i = 2; i < MAXN; ++i)
    if (!visited[i]) {
      prim.push_back(i);
      for (int j = i + i; j < MAXN; j += i) visited[j] = true;
    }
  for (scanf("%d", &q); q--;) {
    scanf("%d", &n);
    int len = get_length(n);
    if (find(prim.begin(), prim.end(), n) == prim.end()) {
      puts("0");
      continue;
    }
    vector<int> v;
    for (int i = 0; i < len - 1; ++i) {
      v.push_back(n % 10);
      n /= 10;
    }
    reverse(v.begin(), v.end());
    dp.clear();
    printf("%d\n", dfs(v));
  }
  return 0;
}
