#include <bits/stdc++.h>
using namespace std;
vector<int> primes;
int n;
int cnt[1000][1000];
int mat[5][5];
bool check(int x) {
  for (int i = 2; i * i <= x; ++i)
    if (x % i == 0) return false;
  return true;
}
int calc(int m) {
  if (m == n) return 1;
  if (n - m == 2) {
    int x = 0, y = 0;
    for (int i = 0; i < m; ++i) {
      x = x * 10 + mat[n - 2][i];
      y = y * 10 + mat[n - 1][i];
    }
    if (cnt[x][y] != -1) return cnt[x][y];
    int &ret = cnt[x][y] = 0;
    x *= 100;
    int l = lower_bound(primes.begin(), primes.end(), x) - primes.begin();
    int r = upper_bound(primes.begin(), primes.end(), x + 99) - primes.begin();
    for (int i = l; i < r; ++i) {
      for (int j = 0, k = primes[i]; j < n; ++j, k /= 10) {
        mat[m][n - j - 1] = k % 10;
        if (n - j - 1 > m) mat[n - j - 1][m] = k % 10;
      }
      ret += calc(m + 1);
    }
    return ret;
  }
  int x = 0, y = 1;
  for (int i = 0; i < m; ++i) x = x * 10 + mat[m][i];
  for (int i = m; i < n; ++i) y *= 10;
  x *= y;
  int l = lower_bound(primes.begin(), primes.end(), x) - primes.begin();
  int r = upper_bound(primes.begin(), primes.end(), x + y - 1) - primes.begin();
  int ret = 0;
  for (int i = l; i < r; ++i) {
    for (int j = 0, k = primes[i]; j < n; ++j, k /= 10) {
      mat[m][n - j - 1] = k % 10;
      if (n - j - 1 > m) mat[n - j - 1][m] = k % 10;
    }
    ret += calc(m + 1);
  }
  return ret;
}
int main() {
  for (int i = 2; i < 100000; ++i)
    if (check(i)) primes.push_back(i);
  memset(cnt, -1, sizeof(cnt));
  int m;
  cin >> m;
  while (m--) {
    int x, y;
    cin >> x;
    y = x;
    for (n = 0; x; x /= 10) {
      mat[0][n] = x % 10;
      n++;
    }
    x = y;
    reverse(mat[0], mat[0] + n);
    for (int i = 0; i < n; ++i) mat[i][0] = mat[0][i];
    cout << calc(1) << endl;
  }
}
