#include <bits/stdc++.h>
using namespace std;
int dp[10][10][10][10][10] = {0};
int sm[10][10][10][10][4] = {0};
bool prime(int n) {
  for (int i = 2; i * i <= n; ++i)
    if (n % i == 0) return false;
  return true;
}
void pre_compute() {
  for (int i = 2; i < 100000; ++i) {
    int pl[5];
    for (int j = 4, ci = i; j >= 0; --j) {
      pl[j] = ci % 10;
      ci /= 10;
    }
    if (prime(i)) {
      dp[pl[0]][pl[1]][pl[2]][pl[3]][pl[4]] = true;
      sm[pl[0]][pl[2]][pl[3]][pl[4]][0]++;
      sm[pl[0]][pl[1]][pl[3]][pl[4]][1]++;
      sm[pl[0]][pl[1]][pl[2]][pl[4]][2]++;
      sm[pl[0]][pl[1]][pl[2]][pl[3]][3]++;
    }
  }
}
int main() {
  int t;
  string s;
  cin >> t;
  pre_compute();
  while (t--) {
    cin >> s;
    int ans = 0;
    vector<int> v(s.size());
    for (int i = 0; i < s.size(); ++i) v[i] = s[i] - '0';
    switch (s.size()) {
      case 2:
        for (int i = 0; i < 10; ++i)
          if (dp[0][0][0][v[1]][i]) ++ans;
        break;
      case 3:
        for (int i = 0; i < 1000; ++i) {
          int w[] = {i / 100, (i / 10) % 10, i % 10};
          if (dp[0][0][v[1]][w[0]][w[1]] && dp[0][0][v[2]][w[1]][w[2]]) ++ans;
        }
        break;
      case 4:
        for (int i = 0; i < 1000000; ++i) {
          int w[6];
          for (int j = 5, ci = i; j >= 0; --j) {
            w[j] = ci % 10;
            ci /= 10;
          }
          if (dp[0][v[1]][w[0]][w[1]][w[2]] && dp[0][v[2]][w[1]][w[3]][w[4]] &&
              dp[0][v[3]][w[2]][w[4]][w[5]])
            ++ans;
        }
        break;
      case 5:
        for (int i = 0; i < 1000000; ++i) {
          int w[6];
          for (int j = 5, ci = i; j >= 0; --j) {
            w[j] = ci % 10;
            ci /= 10;
          }
          int tmp = sm[v[1]][w[0]][w[1]][w[2]][0];
          tmp *= sm[v[2]][w[0]][w[3]][w[4]][1];
          tmp *= sm[v[3]][w[1]][w[3]][w[5]][2];
          tmp *= sm[v[4]][w[2]][w[4]][w[5]][3];
          ans += tmp;
        }
        break;
    }
    cout << ans << endl;
  }
  return 0;
}
