#include <bits/stdc++.h>
using namespace std;
void Ios() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  return;
}
constexpr int kN = int(1E5 + 10);
bitset<kN> not_prime;
vector<int> prime, p2[kN], p3[kN], p4[kN];
int dp1[kN], a[10];
unordered_map<int, int> dp2[kN];
void pre() {
  not_prime.reset();
  for (int i = 2; i < kN; i++) {
    if (!not_prime[i]) prime.push_back(i);
    for (int j : prime) {
      if (i * j >= kN) break;
      not_prime[i * j] = true;
      if (i % j == 0) break;
    }
  }
  int sz = int(prime.size());
  for (int i = 0, C = 10, npos = 0; i < 100000; i += C)
    while (npos < sz && prime[npos] < i + C) {
      if (prime[npos++] >= i) dp1[i]++;
    }
  for (int i = 0, C = 100, npos = 0; i < 100000; i += C)
    while (npos < sz && prime[npos] < i + C) {
      if (prime[npos] >= i)
        p2[i].push_back(prime[npos++]);
      else
        npos++;
    }
  for (int i = 0, C = 1000, npos = 0; i < 100000; i += C)
    while (npos < sz && prime[npos] < i + C) {
      if (prime[npos] >= i)
        p3[i].push_back(prime[npos++]);
      else
        npos++;
    }
  for (int i = 0, C = 10000, npos = 0; i < 100000; i += C)
    while (npos < sz && prime[npos] < i + C) {
      if (prime[npos] >= i)
        p4[i].push_back(prime[npos++]);
      else
        npos++;
    }
  return;
}
long long int dp(int npos) {
  if (npos == 5)
    return dp1[a[5]];
  else if (npos == 4) {
    if (dp2[a[4]].find(a[5]) != dp2[a[4]].end())
      return dp2[a[4]][a[5]];
    else {
      int ans = 0;
      for (int i : p2[a[4]]) ans += dp1[a[5] + (i % 10) * 10];
      return dp2[a[4]][a[5]] = ans;
    }
  } else if (npos == 3) {
    long long int ans = 0;
    for (int i : p3[a[3]]) {
      a[4] += (i / 10) % 10 * 100;
      a[5] += i % 10 * 100;
      ans += dp(npos + 1);
      a[4] -= (i / 10) % 10 * 100;
      a[5] -= i % 10 * 100;
    }
    return ans;
  } else {
    long long int ans = 0;
    for (int i : p4[a[2]]) {
      a[3] += (i / 100) % 10 * 1000;
      a[4] += (i / 10) % 10 * 1000;
      a[5] += i % 10 * 1000;
      ans += dp(npos + 1);
      a[3] -= (i / 100) % 10 * 1000;
      a[4] -= (i / 10) % 10 * 1000;
      a[5] -= i % 10 * 1000;
    }
    return ans;
  }
}
void solve() {
  int n, cnt = 0, tmp;
  scanf("%d", &n);
  tmp = n;
  while (tmp) {
    cnt++;
    tmp /= 10;
  }
  if (cnt == 2)
    printf("%d\n", dp1[n % 10 * 10]);
  else if (cnt == 3) {
    a[4] = n / 10 % 10 * 100;
    a[5] = n % 10 * 100;
    printf("%lld\n", dp(4));
  } else if (cnt == 4) {
    a[3] = n / 100 % 10 * 1000;
    a[4] = n / 10 % 10 * 1000;
    a[5] = n % 10 * 1000;
    printf("%lld\n", dp(3));
  } else {
    a[2] = n / 1000 % 10 * 10000;
    a[3] = n / 100 % 10 * 10000;
    a[4] = n / 10 % 10 * 10000;
    a[5] = n % 10 * 10000;
    printf("%lld\n", dp(2));
  }
  return;
}
int main() {
  int t;
  pre();
  scanf("%d", &t);
  for (int i = 1; i <= t; i++) {
    solve();
  }
}
