#include <bits/stdc++.h>
using namespace std;
int n, ans, d[10];
char str[7][7];
int cnt[7][100000];
bool vis[100000];
int cut(int x, int y) {
  int t = d[y];
  return x - x / t % 10 * t;
}
int sum, t;
void solve() {
  t = 1;
  for (int i = (1); i <= (n - 1); ++i) {
    sum = 0;
    for (int j = 0; j < (n); ++j)
      if (i == j)
        sum += 0;
      else
        sum += d[n - j - 1] * (str[i][j] - '0');
    t *= cnt[n - i - 1][sum];
    if (!t) return;
  }
  ans += t;
}
void dfs(int x, int y) {
  if (x == n - 1) {
    solve();
    return;
  }
  if (y == n) {
    dfs(x + 1, x + 2);
    return;
  }
  for (int i = 0; i < (10); ++i) {
    str[x][y] = str[y][x] = '0' + i;
    dfs(x, y + 1);
  }
}
int main() {
  d[0] = 1;
  for (int i = (1); i <= (7); ++i) d[i] = d[i - 1] * 10;
  memset(cnt, 0, sizeof(cnt));
  memset(vis, 0, sizeof(vis));
  for (int i = 2; i <= 99999; ++i)
    if (!vis[i]) {
      for (int j = 0; j < (6); ++j) ++cnt[j][cut(i, j)];
      for (int j = i + i; j <= 99999; j += i) vis[j] = 1;
    }
  int test;
  cin >> test;
  while (test--) {
    cin >> str[0];
    n = strlen(str[0]);
    for (int i = 0; i < (n); ++i) str[i][0] = str[0][i];
    ans = 0;
    dfs(1, 2);
    cout << ans << endl;
  }
  return 0;
}
