#include <bits/stdc++.h>
using namespace std;
int const N = 100000;
int n;
int ans;
char digits[8][8];
int ten[8];
bitset<N> isprime;
int sum[8];
struct Integer {
  int i, j, x;
  Integer(int i, int j, int x) : i(i), j(j), x(x) {}
  operator int() { return x; }
  Integer(int x = 0) : x(x), i(-1), j(-1) {}
  void operator=(int other) {
    if (i >= 0) {
      sum[i] -= x * ten[n - 1 - j];
      sum[j] -= x * ten[n - 1 - i];
      x = other;
      sum[i] += x * ten[n - 1 - j];
      sum[j] += x * ten[n - 1 - i];
    } else {
      x = other;
    }
  }
};
template <class T>
struct Counter {
  vector<int> bnd;
  vector<T> value;
  Counter<T>(vector<int> bnd) : bnd(bnd), value(bnd.size(), 0) {}
  bool operator++(int) {
    int n = bnd.size();
    int add = -1;
    for (int i = n - 1; i >= 0; --i) {
      if ((int)value[i] != bnd[i] - 1) {
        add = i;
        break;
      }
    }
    if (add == -1) {
      return false;
    }
    value[add] = value[add] + 1;
    for (int i = add + 1; i < n; ++i) {
      value[i] = 0;
    }
    return true;
  }
  T &operator[](int x) { return value[x]; }
};
int count_valid_after_fill[8][N];
int main() {
  isprime.set();
  isprime[0] = isprime[1] = false;
  for (int i = 4; i < isprime.size(); i += 2) isprime[i] = false;
  for (int i = 3; i < isprime.size(); i += 2)
    if (isprime[i]) {
      for (int k = i * 3; k < isprime.size(); k += i + i) isprime[k] = false;
    }
  ten[0] = 1;
  for (int i = 1; i < 8; ++i) {
    ten[i] = ten[i - 1] * 10;
  }
  memset(count_valid_after_fill, 0, (sizeof count_valid_after_fill));
  for (int i = 0; i < isprime.size(); ++i) {
    for (int p = 0; p < 5; ++p) {
      int x = i;
      if (x / ten[p] % 10 == 0) {
        for (int n_ = (10), k = 0; k < n_; ++k) {
          if (x < ((int)(isprime).size()) && isprime[x]) {
            count_valid_after_fill[p][i]++;
          }
          x += ten[p];
        }
      }
    }
  }
  int ca;
  cin >> ca;
  for (int n_ = (ca), ica = 0; ica < n_; ++ica) {
    string input;
    cin >> input;
    n = input.size();
    memset(digits, 0, (sizeof digits));
    memset(sum, 0, (sizeof sum));
    for (int n_ = (n), i = 0; i < n_; ++i) {
      digits[0][i] = digits[i][0] = input[i] - '0';
      sum[0] += ten[n - 1 - i] * digits[i][0];
      if (i != 0) {
        sum[i] += ten[n - 1] * digits[i][0];
      }
    }
    vector<int> bnd((n - 1) * (n - 2) / 2, 10);
    Counter<Integer> counter(bnd);
    int p = 0;
    for (int i = 1; i < n; ++i) {
      for (int j = i + 1; j < n; ++j) {
        counter[p] = Integer(i, j, 0);
        p++;
      }
    }
    int ans = 0;
    do {
      int way = 1;
      for (int i = 1; i < n; ++i) {
        int way2 = count_valid_after_fill[n - 1 - i][sum[i]];
        way *= way2;
      }
      ans += way;
    } while (counter++);
    cout << ans << endl;
  }
  return 0;
}
