#include <bits/stdc++.h>
using namespace std;
bool np[100005];
vector<int> prime;
int cnt[161060];
void sieve(int n) {
  for (int i = (2); i <= (n); i++) {
    if (np[i]) continue;
    prime.push_back(i);
    int t = i;
    int tmp[5];
    for (int j = (0); j <= (4); j++) tmp[j] = t % 10, t /= 10;
    for (int j = (0); j <= (4); j++) {
      int t = 0;
      for (int k = (4); k >= (0); k--) {
        t *= 11;
        if (j == k)
          t += 10;
        else
          t += tmp[k];
      }
      cnt[t]++;
    }
    for (long long j = 1LL * i * i; j <= n; j += i) np[j] = 1;
  }
}
int s;
int fr[6];
long long memo[6][10005];
long long dp(int i, int st) {
  if (memo[i][st] != -1) return memo[i][st];
  int tmp[6];
  for (int j = (0); j <= (5); j++) tmp[j] = st % 10, st /= 10;
  long long res = 0;
  if (s == 2) {
    res = (res + cnt[fr[1] * 11 + 10]) % 1000000007;
  } else if (s == 3) {
    if (i == 2) {
      for (int j = (0); j <= (9); j++) {
        long long c = cnt[fr[1] * 121 + 10 * 11 + j];
        if (!c) continue;
        res = (res + c * dp(i + 1, j)) % 1000000007;
      }
    } else if (i == 3) {
      res = (res + cnt[fr[2] * 121 + tmp[0] * 11 + 10]) % 1000000007;
    }
  } else if (s == 4) {
    if (i == 2) {
      for (int j = (0); j <= (9); j++)
        for (int k = (0); k <= (9); k++) {
          long long c = cnt[fr[1] * 1331 + 10 * 121 + j * 11 + k];
          if (!c) continue;
          res = (res + c * dp(i + 1, k * 10 + j)) % 1000000007;
        }
    } else if (i == 3) {
      for (int j = (0); j <= (9); j++) {
        long long c = cnt[fr[2] * 1331 + tmp[0] * 121 + 10 * 11 + j];
        if (!c) continue;
        res = (res + c * dp(i + 1, j * 10 + tmp[1])) % 1000000007;
      }
    } else if (i == 4) {
      res = (res + cnt[fr[3] * 1331 + tmp[0] * 121 + tmp[1] * 11 + 10]) %
            1000000007;
    }
  } else if (s == 5) {
    if (i == 2) {
      for (int j = (0); j <= (9); j++)
        for (int k = (0); k <= (9); k++)
          for (int l = (0); l <= (9); l++) {
            long long c = cnt[fr[1] * 14641 + 10 * 1331 + j * 121 + k * 11 + l];
            if (!c) continue;
            res = (res + c * dp(i + 1, l * 100 + k * 10 + j)) % 1000000007;
          }
    } else if (i == 3) {
      for (int j = (0); j <= (9); j++)
        for (int k = (0); k <= (9); k++) {
          long long c =
              cnt[fr[2] * 14641 + tmp[0] * 1331 + 10 * 121 + j * 11 + k];
          if (!c) continue;
          res =
              (res + c * dp(i + 1, k * 1000 + tmp[2] * 100 + j * 10 + tmp[1])) %
              1000000007;
        }
    } else if (i == 4) {
      for (int j = (0); j <= (9); j++) {
        long long c =
            cnt[fr[3] * 14641 + tmp[0] * 1331 + tmp[1] * 121 + 10 * 11 + j];
        if (!c) continue;
        res =
            (res + c * dp(i + 1, j * 100 + tmp[3] * 10 + tmp[2])) % 1000000007;
      }
    } else if (i == 5) {
      res = (res + cnt[fr[4] * 14641 + tmp[0] * 1331 + tmp[1] * 121 +
                       tmp[2] * 11 + 10]) %
            1000000007;
    }
  }
  return memo[i][st] = res;
}
int main() {
  sieve(100000);
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  for (int i = (1); i <= (t); i++) {
    string S;
    cin >> S;
    s = S.length();
    for (int j = (0); j <= (s - 1); j++) fr[j] = S[j] - '0';
    memset(memo, -1, sizeof(memo));
    printf("%lld\n", dp(2, 0));
  }
  return 0;
}
