#include <bits/stdc++.h>
long long max(long long a, long long b) { return (a < b) ? b : a; }
long long min(long long a, long long b) { return (a > b) ? b : a; }
using namespace std;
long long gcd(long long a, long long b) {
  return (a % b == 0) ? b : gcd(b, a % b);
}
long long p[100100];
vector<long long> dp[7][100000];
long long mat[10];
long long solve(long long ind, long long pr) {
  if (ind == 2) return dp[1][mat[0] * 10 + pr % 10].size();
  long long ret = 0;
  for (long long i = 0; i < ind; i++) mat[i] *= 10, mat[i] += pr % 10, pr /= 10;
  for (long long i = 0; i < dp[ind - 1][mat[ind - 2]].size(); i++)
    ret += solve(ind - 1, dp[ind - 1][mat[ind - 2]][i]);
  for (long long i = 0; i < ind; i++) mat[i] /= 10;
  return ret;
}
int main() {
  long long q;
  cin >> q;
  for (long long i = 2; i < 100000; i++) {
    if (!p[i]) {
      long long t = i / 10;
      for (long long j = 1; j < 5; j++) {
        dp[j][t].push_back(i);
        t /= 10;
      }
      for (long long j = i * i; j < 100000; j += i) p[j] = 1;
    }
  }
  for (long long asd = 0; asd < q; asd++) {
    long long t;
    scanf("%lld", &t);
    cout << solve(log10(t) + 1, t) << endl;
  }
}
