#include <bits/stdc++.h>
using namespace std;
vector<int> a[100000][6];
bool pr[100000];
int b[6][6];
int d[6];
int n;
int res;
void rec(int x) {
  if (x == n) {
    ++res;
    return;
  }
  for (int i = (0); i < (((int)(a[d[x]][n - x]).size())); ++i) {
    int g = a[d[x]][n - x][i];
    bool good = true;
    for (int j = n - 1; j > x; --j) {
      d[j] = d[j] * 10 + g % 10;
      if (!((int)(a[d[j]][n - x - 1]).size())) good = false;
      g /= 10;
    }
    if (good) rec(x + 1);
    for (int j = n - 1; j > x; --j) {
      d[j] /= 10;
    }
  }
}
int main() {
  for (int i = (2); i < (100000); ++i)
    if (!pr[i]) {
      for (int j = 2; i * j < 100000; ++j) {
        pr[i * j] = true;
      }
      for (int d = 10000, num = 4; num >= 0; d /= 10, num--) {
        a[i / d][num].push_back(i);
      }
    }
  int t;
  cin >> t;
  for (int i = (0); i < (t); ++i) {
    string p;
    cin >> p;
    for (int j = (0); j < (((int)(p).size())); ++j) d[j] = p[j] - '0';
    n = ((int)(p).size());
    res = 0;
    rec(1);
    cout << res << endl;
  }
  return 0;
}
