#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const double EPS = 1e-9;
int primes[100000];
int dig[100000][5];
int fst[1000000];
int cntP = 0;
bool isPrime(int x) {
  for (int i = 2; i * i <= x; ++i) {
    if (x % i == 0) return false;
  }
  return true;
}
int len;
int M[5][5];
int rec(int pos) {
  int l, r;
  l = 0;
  for (int i = 0; i < pos; ++i) {
    l *= 10;
    l += M[pos][i];
  }
  r = l + 1;
  for (int i = pos; i < len; ++i) {
    r *= 10;
    l *= 10;
  }
  int d = fst[l];
  int ans = 0;
  if (pos == len - 1) {
    while (d < cntP && primes[d] < r) {
      ++d;
      ++ans;
    }
    return ans;
  }
  while (d < cntP && primes[d] < r) {
    int l = 0;
    for (int i = len - 1; i >= pos; --i) {
      M[i][pos] = dig[d][l];
      ++l;
    }
    ans += rec(pos + 1);
    ++d;
  }
  return ans;
}
int q[100000];
int solve(int p) {
  if (q[p] != -1) {
    return q[p];
  }
  int x = p;
  len = 0;
  while (x) {
    x /= 10;
    ++len;
  }
  x = p;
  for (int i = len - 1; i >= 0; --i) {
    M[0][i] = M[i][0] = x % 10;
    x /= 10;
  }
  return rec(1);
}
void init() {
  memset(q, 0xff, sizeof(q));
  q[98009] = 1251925;
  q[97007] = 1169507;
  q[97003] = 1420177;
  q[97001] = 1420658;
  q[96001] = 1390741;
  q[95009] = 1306271;
  q[95003] = 1459996;
  q[94009] = 1306432;
  q[94007] = 1199076;
  q[93001] = 1510566;
  q[92009] = 1398025;
  q[92003] = 1562355;
  q[91009] = 1457928;
  q[90907] = 1142536;
  q[90901] = 1393261;
  q[90803] = 1387258;
  q[90709] = 1276206;
  q[90703] = 1423938;
  q[90407] = 1204532;
  q[90403] = 1459875;
  q[90401] = 1468633;
  q[90203] = 1555640;
  q[90107] = 1339119;
  q[90089] = 1247792;
  q[90073] = 1440153;
  q[90071] = 1431231;
  q[90067] = 1141975;
  q[90059] = 1315153;
  q[90053] = 1470744;
  q[90031] = 1524892;
  q[90023] = 1563816;
  q[90019] = 1472637;
  q[90017] = 1346537;
  q[90011] = 1642544;
  q[90007] = 1607029;
  q[90001] = 1961753;
  q[89009] = 1246094;
  q[89003] = 1390038;
  q[88007] = 1145413;
  q[88003] = 1398091;
  q[88001] = 1399182;
  q[85009] = 1306271;
  q[83009] = 1360770;
  q[83003] = 1515911;
  q[82009] = 1398025;
  q[82007] = 1285515;
  q[82003] = 1562355;
  q[81001] = 1631654;
  q[80909] = 1247473;
  q[80809] = 1248499;
  q[80803] = 1387258;
  q[80701] = 1430093;
  q[80603] = 1388751;
  q[80407] = 1204532;
  q[80309] = 1359505;
  q[80209] = 1396097;
  q[80207] = 1277733;
  q[80107] = 1339119;
  q[80077] = 1175152;
  q[80071] = 1431231;
  q[80051] = 1468076;
  q[80039] = 1364989;
  q[80021] = 1563949;
  q[78007] = 1145413;
  q[77003] = 1420177;
  q[76003] = 1388563;
  q[76001] = 1390741;
  q[73009] = 1360770;
  q[70901] = 1393261;
  q[70709] = 1276206;
  q[70607] = 1140912;
  q[70507] = 1196026;
  q[70501] = 1459995;
  q[70309] = 1359505;
  q[70207] = 1277733;
  q[70201] = 1557468;
  q[70099] = 1256244;
  q[70079] = 1286779;
  q[70067] = 1141975;
  q[70061] = 1393926;
  q[70051] = 1468076;
  q[70039] = 1364989;
  q[70019] = 1472637;
  q[70009] = 1755692;
  q[70003] = 1958462;
  q[70001] = 1961753;
  q[69001] = 1391045;
  q[67003] = 1420177;
  q[65003] = 1459996;
  q[64007] = 1199076;
  q[62003] = 1562355;
  q[61007] = 1336465;
  q[61001] = 1631654;
  q[60901] = 1393261;
  q[60703] = 1423938;
  q[60607] = 1140912;
  q[60601] = 1392479;
  q[60509] = 1309767;
  q[60209] = 1396097;
  q[60107] = 1339119;
  q[60103] = 1629683;
  q[60101] = 1634767;
  q[60091] = 1397331;
  q[60089] = 1247792;
  q[60083] = 1396317;
  q[60077] = 1175152;
  q[60041] = 1475531;
  q[60037] = 1250842;
  q[60029] = 1400424;
  q[60017] = 1346537;
  q[60013] = 1642902;
  q[59009] = 1246094;
  q[56009] = 1244219;
  q[56003] = 1388563;
  q[55009] = 1306271;
  q[55001] = 1467545;
  q[54001] = 1456227;
  q[53003] = 1515911;
  q[52009] = 1398025;
  q[51001] = 1631654;
  q[50909] = 1247473;
  q[50707] = 1173686;
  q[50503] = 1455379;
  q[50207] = 1277733;
  q[50101] = 1634767;
  q[50093] = 1396686;
  q[50087] = 1140795;
  q[50077] = 1175152;
  q[50069] = 1247971;
  q[50053] = 1470744;
  q[50051] = 1468076;
  q[50047] = 1209842;
  q[50033] = 1529744;
  q[50023] = 1563816;
  q[50021] = 1563949;
  q[49009] = 1246094;
  q[49003] = 1390038;
  q[45007] = 1205884;
  q[43003] = 1515911;
  q[40903] = 1394074;
  q[40801] = 1388142;
  q[40709] = 1276206;
  q[40609] = 1246446;
  q[40507] = 1196026;
  q[40099] = 1256244;
  q[40093] = 1396686;
  q[40087] = 1140795;
  q[40063] = 1393792;
  q[40039] = 1364989;
  q[40037] = 1250842;
  q[40031] = 1524892;
  q[40013] = 1642902;
  q[40009] = 1755692;
  q[37003] = 1420177;
  q[36007] = 1139248;
  q[32009] = 1398025;
  q[32003] = 1562355;
  q[30809] = 1248499;
  q[30803] = 1387258;
  q[30707] = 1173686;
  q[30703] = 1423938;
  q[30509] = 1309767;
  q[30403] = 1459875;
  q[30307] = 1249397;
  q[30203] = 1555640;
  q[30109] = 1462415;
  q[30103] = 1629683;
  q[30097] = 1146833;
  q[30091] = 1397331;
  q[30089] = 1247792;
  q[30071] = 1431231;
  q[30059] = 1315153;
  q[30047] = 1209842;
  q[30029] = 1400424;
  q[30013] = 1642902;
  q[30011] = 1642544;
  q[29009] = 1246094;
  q[28001] = 1399182;
  q[26003] = 1388563;
  q[24007] = 1199076;
  q[24001] = 1456227;
  q[23003] = 1515911;
  q[22003] = 1562355;
  q[21001] = 1631654;
  q[20903] = 1394074;
  q[20809] = 1248499;
  q[20807] = 1138381;
  q[20707] = 1173686;
  q[20509] = 1309767;
  q[20507] = 1196026;
  q[20407] = 1204532;
  q[20201] = 1557468;
  q[20107] = 1339119;
  q[20101] = 1634767;
  q[20089] = 1247792;
  q[20071] = 1431231;
  q[20063] = 1393792;
  q[20051] = 1468076;
  q[20047] = 1209842;
  q[20029] = 1400424;
  q[20023] = 1563816;
  q[20021] = 1563949;
  q[20011] = 1642544;
  q[19009] = 1246094;
  q[19001] = 1391045;
  q[16007] = 1139248;
  q[16001] = 1390741;
  q[14009] = 1306432;
  q[13009] = 1360770;
  q[13007] = 1232449;
  q[13003] = 1515911;
  q[13001] = 1510566;
  q[12007] = 1285515;
  q[11003] = 1628066;
  q[10909] = 1247473;
  q[10903] = 1394074;
  q[10709] = 1276206;
  q[10607] = 1140912;
  q[10601] = 1392479;
  q[10501] = 1459995;
  q[10303] = 1517597;
  q[10301] = 1525636;
  q[10103] = 1629683;
  q[10099] = 1256244;
  q[10093] = 1396686;
  q[10091] = 1397331;
  q[10079] = 1286779;
  q[10069] = 1247971;
  q[10067] = 1141975;
  q[10061] = 1393926;
  q[10039] = 1364989;
  q[10037] = 1250842;
  q[10009] = 1755692;
  q[10007] = 1607029;
  q[9007] = 1962;
  q[9001] = 2834;
  q[8009] = 3030;
  q[7001] = 2834;
  q[6007] = 1962;
  q[5009] = 3030;
  q[5003] = 3351;
  q[4007] = 1962;
  q[4003] = 3351;
  q[4001] = 2834;
  q[3001] = 2834;
  q[2003] = 3351;
  q[1009] = 3030;
}
int main() {
  int T;
  init();
  for (int i = 2; i < 100000; ++i) {
    if (isPrime(i)) {
      int x = i;
      int l = 0;
      while (x) {
        dig[cntP][l] = x % 10;
        ++l;
        x /= 10;
      }
      primes[cntP++] = i;
    }
  }
  int cur = cntP;
  for (int i = 99999; i >= 0; --i) {
    if (cur > 0 && i == primes[cur - 1]) --cur;
    fst[i] = cur;
  }
  scanf("%d", &T);
  for (int i = 0; i < T; ++i) {
    int x;
    scanf("%d", &x);
    printf("%d\n", solve(x));
  }
  return 0;
}
