#include <bits/stdc++.h>
using namespace std;
int t, a, ans;
vector<int> p;
int matrix[6], power[6];
int cnt[10000];
int solve(int cur, int n) {
  if (cur == n - 1) return cnt[matrix[cur]];
  int ret = 0;
  int l = matrix[cur], r = l + 1;
  int L = 0, R = p.size() - 1;
  while (L < R) {
    int mid = (L + R) >> 1;
    if (l * power[n - cur] > p[mid])
      L = mid + 1;
    else
      R = mid;
  }
  while (L < p.size() && p[L] < r * power[n - cur]) {
    int t = p[L];
    for (int i = n - 1; i >= cur; i--) {
      matrix[i] = matrix[i] * 10 + t % 10;
      t /= 10;
    }
    ret += solve(cur + 1, n);
    L++;
    for (int i = cur; i < n; i++) matrix[i] /= 10;
  }
  return ret;
}
int main() {
  p.push_back(2);
  for (int i = 3; i < 100000; i++) {
    bool flag = 1;
    for (int j = 0; j < p.size() && p[j] * p[j] <= i; j++)
      if (i % p[j] == 0) {
        flag = 0;
        break;
      }
    if (flag) p.push_back(i);
  }
  for (int i = 0; i < p.size(); i++) cnt[p[i] / 10]++;
  power[0] = 1;
  for (int i = 1; i < 6; i++) power[i] = power[i - 1] * 10;
  cin >> t;
  while (t--) {
    cin >> a;
    int n = 0, t = a;
    while (t) {
      n++;
      t /= 10;
    }
    t = a;
    for (int i = 0; i < n; i++) {
      matrix[n - 1 - i] = t % 10;
      t /= 10;
    }
    ans = solve(1, n);
    cout << ans << endl;
  }
  return 0;
}
