#include <bits/stdc++.h>
using namespace std;
const int N = 100000;
const int G = 6;
int n;
bool primes[N];
vector<int> primeGroups[G][N];
int search(int depth, int groups[G]) {
  if (depth == n) return 1;
  int total = 0;
  int g = groups[depth];
  int primeCount = primeGroups[n - depth][g].size();
  for (int i = 0; i < primeCount; i++) {
    int prime = primeGroups[n - depth][g][i];
    int newGroup[G];
    for (int j = n - 1; j > depth; j--) {
      int div = prime / 10;
      newGroup[j] = groups[j] * 10 + prime - 10 * div;
      prime = div;
    }
    total += search(depth + 1, newGroup);
  }
  return total;
}
int main() {
  primes[0] = primes[1] = true;
  for (int i = 0; i < N; i++) {
    if (!primes[i]) {
      int ic = i / 10;
      for (int j = 1; j < G; j++) {
        primeGroups[j][ic].push_back(i);
        ic /= 10;
      }
      for (int j = i + i; j < N; j += i) primes[j] = true;
    }
  }
  int t;
  cin >> t;
  for (int ti = 0; ti < t; ti++) {
    string p;
    cin >> p;
    n = p.length();
    int groups[G];
    for (int i = 0; i < n; i++) groups[i] = p[i] - '0';
    cout << search(1, groups) << endl;
  }
}
