#include <bits/stdc++.h>
using namespace std;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);
const int PRIME_SIZE = 99999;
int psize;
bitset<PRIME_SIZE + 1> bprime;
int prime[PRIME_SIZE / 10 + 1000];
int Eratosthenes(int n) {
  psize = 0;
  bprime.set();
  bprime[0] = bprime[1] = false;
  for (int i = 2; i <= n; i++) {
    if (!bprime[i]) {
      continue;
    }
    prime[psize++] = i;
    if ((long long)i * i > n) {
      continue;
    }
    for (int j = i * i; j <= n; j += i) {
      bprime[j] = false;
    }
  }
  return psize;
}
int s;
int seq[100];
int matrix[10][10];
int myPow10[10];
long long ans;
char cnt[20001][2001];
void Print() {
  for (int y = 0; y < (int)(s); y++) {
    for (int x = 0; x < (int)(s); x++) {
      printf("%2d", matrix[y][x]);
    }
    puts("");
  }
  puts("");
}
bool Set(int y, int v) {
  for (int x = s - 1; x >= 0; x--) {
    int c = v % 10;
    if (matrix[y][x] != -1 && matrix[y][x] != c) {
      return false;
    }
    matrix[y][x] = c;
    matrix[x][y] = c;
    v /= 10;
  }
  return true;
}
long long calc(int y, int x) {
  long long ret = 0;
  if (y >= s) {
    return 1;
  }
  if (x >= s) {
    int left = myPow10[y];
    int right = myPow10[s - y - 1];
    for (int j = 0; j < (int)(s); j++) {
      if (j == y) {
        continue;
      }
      assert(matrix[y][j] >= 0);
      if (j < y) {
        left += matrix[y][j] * myPow10[y - j - 1];
      } else {
        right += matrix[y][j] * myPow10[s - j - 1];
      }
    }
    ret = cnt[left][right];
    if (ret != 0) {
      ret *= calc(y + 1, y + 2);
    }
  } else {
    for (int i = 0; i < (int)(10); i++) {
      matrix[y][x] = matrix[x][y] = i;
      ret += calc(y, x + 1);
    }
  }
  return ret;
}
int main() {
  Eratosthenes(PRIME_SIZE);
  myPow10[0] = 1;
  for (int i = 0; i < (int)(9); i++) {
    myPow10[i + 1] = myPow10[i] * 10;
  }
  for (int i = 0; i < (int)(psize); i++) {
    int v = prime[i];
    for (int s = (1); s <= (int)(5); s++) {
      if (v >= myPow10[s]) {
        continue;
      }
      for (int i = 0; i < (int)(s - 1); i++) {
        int left = myPow10[s - i - 1];
        int right = myPow10[i];
        for (int j = 0; j < (int)(s); j++) {
          if (j == i) {
            continue;
          }
          if (j > i) {
            left += v / myPow10[j] % 10 * myPow10[j - i - 1];
          } else {
            right += v / myPow10[j] % 10 * myPow10[j];
          }
        }
        assert(left <= 20000 && right <= 2000);
        cnt[left][right]++;
      }
    }
  }
  int n;
  scanf("%d", &n);
  for (int i = 0; i < (int)(n); i++) {
    scanf("%d", &seq[i]);
  }
  for (int i = 0; i < (int)(n); i++) {
    memset((matrix), -1, sizeof(matrix));
    s = 0;
    {
      int v = seq[i];
      while (v != 0) {
        v /= 10;
        s++;
      }
    }
    if (s == 1) {
      ans = 1;
    } else {
      Set(0, seq[i]);
      ans = calc(1, 2);
    }
    cout << ans << endl;
  }
}
