#include <bits/stdc++.h>
using namespace std;
const int MAXp = 100000;
int p, d;
int p10[8];
int dig[8];
bool ip[MAXp];
int num[8];
vector<int> v[6][10][6][MAXp / 100];
int ans = 0;
void init() {
  p10[0] = 1;
  for (int i = 1; i < 8; i++) p10[i] = p10[i - 1] * 10;
  ip[0] = ip[1] = 1;
  for (int i = 2; i < MAXp; i++)
    if (!ip[i]) {
      for (int d = (1), _n = (5); d <= _n; d++)
        for (int y = (0), _n = (min(d, 3)); y <= _n; y++)
          if (i / p10[d - 1] < 10)
            v[d][i / p10[d - 1]][y][i % p10[y]].push_back(i);
      if (i < 1000)
        for (long long j = i * i; j < MAXp; j += i) ip[j] = 1;
    }
}
void bt(int r) {
  if (r == 0) {
    ans++;
    return;
  }
  vector<int> &f = v[d][dig[r]][d - r - 1][num[r]];
  int z = int((f).size());
  int c = d - r - 1;
  for (int i = 0, _n = (z); i < _n; i++) {
    int x = f[i];
    for (int j = (1), _n = (r - 1); j <= _n; j++)
      num[j] += (x / p10[d - j - 1] % 10) * p10[c];
    bt(r - 1);
    for (int j = (1), _n = (r - 1); j <= _n; j++)
      num[j] -= (x / p10[d - j - 1] % 10) * p10[c];
  }
}
int main() {
  init();
  int ts;
  for (cin >> ts; ts--;) {
    cin >> p;
    int tmp = p;
    d = 0;
    while (tmp) dig[d++] = tmp % 10, tmp /= 10;
    reverse(dig, dig + d);
    ans = 0;
    bt(d - 1);
    cout << ans << endl;
  }
  {
    int _;
    cin >> _;
  }
}
