Problem: Polycarpus has t safes. The password for each safe is a square matrix consisting of decimal digits '0' ... '9' (the sizes of passwords to the safes may vary). Alas, Polycarpus has forgotten all passwords, so now he has to restore them.

Polycarpus enjoys prime numbers, so when he chose the matrix passwords, he wrote a prime number in each row of each matrix. To his surprise, he found that all the matrices turned out to be symmetrical (that is, they remain the same after transposition). Now, years later, Polycarp was irritated to find out that he remembers only the prime numbers pi, written in the first lines of the password matrices.

For each safe find the number of matrices which can be passwords to it.

The number of digits in pi determines the number of rows and columns of the i-th matrix. One prime number can occur in several rows of the password matrix or in several matrices. The prime numbers that are written not in the first row of the matrix may have leading zeros.

Input

The first line of the input contains an integer t (1 ≤ t ≤ 30) — the number of safes. Next t lines contain integers pi (10 ≤ pi ≤ 99999), pi is a prime number written in the first row of the password matrix for the i-th safe. All pi's are written without leading zeros.

Output

Print t numbers, the i-th of them should be the number of matrices that can be a password to the i-th safe. Print the numbers on separate lines.

Examples

Input

4
11
239
401
9001


Output

4
28
61
2834

Note

Here is a possible password matrix for the second safe: 
    
    
      
    239  
    307  
    977  
    

Here is a possible password matrix for the fourth safe: 
    
    
      
    9001  
    0002  
    0002  
    1223   
    

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
bool not_prime[N] = {1, 1, 0};
vector<int> P[5][N];
int depth, cnt, num, ans[6][6], res[N] = {0};
void init() {
  res[2] = 1;
  res[3] = 1;
  res[5] = 1;
  res[7] = 1;
  res[11] = 4;
  res[13] = 2;
  res[17] = 3;
  res[19] = 1;
  res[23] = 2;
  res[29] = 1;
  res[31] = 4;
  res[37] = 3;
  res[41] = 4;
  res[43] = 2;
  res[47] = 3;
  res[53] = 2;
  res[59] = 1;
  res[61] = 4;
  res[67] = 3;
  res[71] = 4;
  res[73] = 2;
  res[79] = 1;
  res[83] = 2;
  res[89] = 1;
  res[97] = 3;
  res[101] = 61;
  res[103] = 48;
  res[107] = 33;
  res[109] = 41;
  res[113] = 42;
  res[127] = 21;
  res[131] = 42;
  res[137] = 20;
  res[139] = 28;
  res[149] = 31;
  res[151] = 35;
  res[157] = 18;
  res[163] = 35;
  res[167] = 21;
  res[173] = 27;
  res[179] = 25;
  res[181] = 39;
  res[191] = 30;
  res[193] = 30;
  res[197] = 16;
  res[199] = 26;
  res[211] = 52;
  res[223] = 34;
  res[227] = 21;
  res[229] = 27;
  res[233] = 30;
  res[239] = 28;
  res[241] = 44;
  res[251] = 35;
  res[257] = 18;
  res[263] = 35;
  res[269] = 27;
  res[271] = 36;
  res[277] = 17;
  res[281] = 39;
  res[283] = 29;
  res[293] = 30;
  res[307] = 33;
  res[311] = 52;
  res[313] = 42;
  res[317] = 26;
  res[331] = 42;
  res[337] = 20;
  res[347] = 20;
  res[349] = 31;
  res[353] = 28;
  res[359] = 24;
  res[367] = 21;
  res[373] = 27;
  res[379] = 25;
  res[383] = 29;
  res[389] = 26;
  res[397] = 16;
  res[401] = 61;
  res[409] = 41;
  res[419] = 37;
  res[421] = 38;
  res[431] = 42;
  res[433] = 30;
  res[439] = 28;
  res[443] = 33;
  res[449] = 31;
  res[457] = 18;
  res[461] = 36;
  res[463] = 35;
  res[467] = 21;
  res[479] = 25;
  res[487] = 19;
  res[491] = 30;
  res[499] = 26;
  res[503] = 48;
  res[509] = 41;
  res[521] = 38;
  res[523] = 34;
  res[541] = 44;
  res[547] = 20;
  res[557] = 18;
  res[563] = 35;
  res[569] = 27;
  res[571] = 36;
  res[577] = 17;
  res[587] = 19;
  res[593] = 30;
  res[599] = 26;
  res[601] = 61;
  res[607] = 33;
  res[613] = 42;
  res[617] = 26;
  res[619] = 37;
  res[631] = 42;
  res[641] = 44;
  res[643] = 33;
  res[647] = 20;
  res[653] = 28;
  res[659] = 24;
  res[661] = 36;
  res[673] = 27;
  res[677] = 17;
  res[683] = 29;
  res[691] = 30;
  res[701] = 61;
  res[709] = 41;
  res[719] = 37;
  res[727] = 21;
  res[733] = 30;
  res[739] = 28;
  res[743] = 33;
  res[751] = 35;
  res[757] = 18;
  res[761] = 36;
  res[769] = 27;
  res[773] = 27;
  res[787] = 19;
  res[797] = 16;
  res[809] = 41;
  res[811] = 52;
  res[821] = 38;
  res[823] = 34;
  res[827] = 21;
  res[829] = 27;
  res[839] = 28;
  res[853] = 28;
  res[857] = 18;
  res[859] = 24;
  res[863] = 35;
  res[877] = 17;
  res[881] = 39;
  res[883] = 29;
  res[887] = 19;
  res[907] = 33;
  res[911] = 52;
  res[919] = 37;
  res[929] = 27;
  res[937] = 20;
  res[941] = 44;
  res[947] = 20;
  res[953] = 28;
  res[967] = 21;
  res[971] = 36;
  res[977] = 17;
  res[983] = 29;
  res[991] = 30;
  res[997] = 16;
  res[1009] = 3030;
  res[1013] = 2762;
  res[1019] = 2459;
  res[1021] = 2103;
  res[1031] = 1983;
  res[1033] = 2446;
  res[1039] = 2121;
  res[1049] = 2183;
  res[1051] = 1852;
  res[1061] = 1888;
  res[1063] = 2382;
  res[1069] = 2068;
  res[1087] = 1279;
  res[1091] = 1792;
  res[1093] = 2320;
  res[1097] = 1275;
  res[1103] = 2627;
  res[1109] = 2418;
  res[1117] = 1298;
  res[1123] = 2025;
  res[1129] = 1852;
  res[1151] = 1548;
  res[1153] = 1853;
  res[1163] = 1946;
  res[1171] = 1497;
  res[1181] = 1510;
  res[1187] = 1084;
  res[1193] = 1839;
  res[1201] = 2110;
  res[1213] = 2049;
  res[1217] = 1180;
  res[1223] = 1878;
  res[1229] = 1686;
  res[1231] = 1524;
  res[1237] = 1050;
  res[1249] = 1598;
  res[1259] = 1541;
  res[1277] = 942;
  res[1279] = 1486;
  res[1283] = 1630;
  res[1289] = 1462;
  res[1291] = 1376;
  res[1297] = 951;
  res[1301] = 2075;
  res[1303] = 2376;
  res[1307] = 1412;
  res[1319] = 1729;
  res[1321] = 1541;
  res[1327] = 1056;
  res[1361] = 1397;
  res[1367] = 971;
  res[1373] = 1440;
  res[1381] = 1341;
  res[1399] = 1399;
  res[1409] = 2171;
  res[1423] = 1801;
  res[1427] = 1025;
  res[1429] = 1678;
  res[1433] = 1712;
  res[1439] = 1544;
  res[1447] = 1002;
  res[1451] = 1318;
  res[1453] = 1625;
  res[1459] = 1466;
  res[1471] = 1286;
  res[1481] = 1263;
  res[1483] = 1585;
  res[1487] = 903;
  res[1489] = 1453;
  res[1493] = 1600;
  res[1499] = 1402;
  res[1511] = 1492;
  res[1523] = 1692;
  res[1531] = 1353;
  res[1543] = 1589;
  res[1549] = 1462;
  res[1553] = 1572;
  res[1559] = 1379;
  res[1567] = 914;
  res[1571] = 1214;
  res[1579] = 1312;
  res[1583] = 1478;
  res[1597] = 852;
  res[1601] = 1883;
  res[1607] = 1311;
  res[1609] = 2051;
  res[1613] = 1847;
  res[1619] = 1725;
  res[1621] = 1496;
  res[1627] = 1009;
  res[1637] = 954;
  res[1657] = 878;
  res[1663] = 1606;
  res[1667] = 922;
  res[1669] = 1431;
  res[1693] = 1566;
  res[1697] = 886;
  res[1699] = 1371;
  res[1709] = 1920;
  res[1721] = 1357;
  res[1723] = 1641;
  res[1733] = 1567;
  res[1741] = 1278;
  res[1747] = 926;
  res[1753] = 1515;
  res[1759] = 1275;
  res[1777] = 812;
  res[1783] = 1446;
  res[1787] = 845;
  res[1789] = 1250;
  res[1801] = 1885;
  res[1811] = 1521;
  res[1823] = 1636;
  res[1831] = 1341;
  res[1847] = 944;
  res[1861] = 1326;
  res[1867] = 867;
  res[1871] = 1216;
  res[1873] = 1327;
  res[1877] = 830;
  res[1879] = 1271;
  res[1889] = 1276;
  res[1901] = 1934;
  res[1907] = 1294;
  res[1913] = 1753;
  res[1931] = 1359;
  res[1933] = 1563;
  res[1949] = 1414;
  res[1951] = 1254;
  res[1973] = 1308;
  res[1979] = 1263;
  res[1987] = 813;
  res[1993] = 1532;
  res[1997] = 863;
  res[1999] = 1331;
  res[2003] = 3351;
  res[2011] = 2194;
  res[2017] = 1598;
  res[2027] = 1452;
  res[2029] = 2280;
  res[2039] = 2121;
  res[2053] = 2347;
  res[2063] = 2382;
  res[2069] = 2068;
  res[2081] = 1793;
  res[2083] = 2241;
  res[2087] = 1279;
  res[2089] = 1989;
  res[2099] = 1984;
  res[2111] = 1847;
  res[2113] = 2169;
  res[2129] = 1852;
  res[2131] = 1666;
  res[2137] = 1099;
  res[2141] = 1635;
  res[2143] = 1956;
  res[2153] = 1853;
  res[2161] = 1606;
  res[2179] = 1581;
  res[2203] = 2511;
  res[2207] = 1428;
  res[2213] = 2049;
  res[2221] = 1598;
  res[2237] = 1050;
  res[2239] = 1618;
  res[2243] = 1777;
  res[2251] = 1427;
  res[2267] = 998;
  res[2269] = 1587;
  res[2273] = 1573;
  res[2281] = 1383;
  res[2287] = 954;
  res[2293] = 1735;
  res[2297] = 951;
  res[2309] = 2138;
  res[2311] = 1629;
  res[2333] = 1698;
  res[2339] = 1486;
  res[2341] = 1417;
  res[2347] = 985;
  res[2351] = 1380;
  res[2357] = 918;
  res[2371] = 1325;
  res[2377] = 903;
  res[2381] = 1341;
  res[2383] = 1579;
  res[2389] = 1387;
  res[2393] = 1647;
  res[2399] = 1399;
  res[2411] = 1562;
  res[2417] = 1140;
  res[2423] = 1801;
  res[2437] = 985;
  res[2441] = 1376;
  res[2447] = 1002;
  res[2459] = 1466;
  res[2467] = 977;
  res[2473] = 1470;
  res[2477] = 899;
  res[2503] = 2238;
  res[2521] = 1433;
  res[2531] = 1353;
  res[2539] = 1438;
  res[2543] = 1589;
  res[2549] = 1462;
  res[2551] = 1303;
  res[2557] = 873;
  res[2579] = 1312;
  res[2591] = 1249;
  res[2593] = 1541;
  res[2609] = 2051;
  res[2617] = 1100;
  res[2621] = 1496;
  res[2633] = 1634;
  res[2647] = 1015;
  res[2657] = 878;
  res[2659] = 1398;
  res[2663] = 1606;
  res[2671] = 1277;
  res[2677] = 892;
  res[2683] = 1541;
  res[2687] = 926;
  res[2689] = 1389;
  res[2693] = 1566;
  res[2699] = 1371;
  res[2707] = 1259;
  res[2711] = 1476;
  res[2713] = 1776;
  res[2719] = 1558;
  res[2729] = 1448;
  res[2731] = 1290;
  res[2741] = 1278;
  res[2749] = 1381;
  res[2753] = 1515;
  res[2767] = 858;
  res[2777] = 812;
  res[2789] = 1250;
  res[2791] = 1191;
  res[2797] = 819;
  res[2801] = 1885;
  res[2803] = 2172;
  res[2819] = 1600;
  res[2833] = 1579;
  res[2837] = 893;
  res[2843] = 1544;
  res[2851] = 1261;
  res[2857] = 865;
  res[2861] = 1326;
  res[2879] = 1271;
  res[2887] = 886;
  res[2897] = 872;
  res[2903] = 2153;
  res[2909] = 2004;
  res[2917] = 1060;
  res[2927] = 952;
  res[2939] = 1398;
  res[2953] = 1477;
  res[2957] = 847;
  res[2963] = 1571;
  res[2969] = 1371;
  res[2971] = 1199;
  res[2999] = 1331;
  res[3001] = 2834;
  res[3011] = 2194;
  res[3019] = 2459;
  res[3023] = 2564;
  res[3037] = 1382;
  res[3041] = 1940;
  res[3049] = 2183;
  res[3061] = 1888;
  res[3067] = 1354;
  res[3079] = 1951;
  res[3083] = 2241;
  res[3089] = 1989;
  res[3109] = 2418;
  res[3119] = 1921;
  res[3121] = 1766;
  res[3137] = 1099;
  res[3163] = 1946;
  res[3167] = 1102;
  res[3169] = 1725;
  res[3181] = 1510;
  res[3187] = 1084;
  res[3191] = 1497;
  res[3203] = 2511;
  res[3209] = 2273;
  res[3217] = 1180;
  res[3221] = 1598;
  res[3229] = 1686;
  res[3251] = 1427;
  res[3253] = 1755;
  res[3257] = 984;
  res[3259] = 1541;
  res[3271] = 1377;
  res[3299] = 1479;
  res[3301] = 2075;
  res[3307] = 1412;
  res[3313] = 1943;
  res[3319] = 1729;
  res[3323] = 1807;
  res[3329] = 1622;
  res[3331] = 1449;
  res[3343] = 1707;
  res[3347] = 985;
  res[3359] = 1408;
  res[3361] = 1397;
  res[3371] = 1325;
  res[3373] = 1440;
  res[3389] = 1387;
  res[3391] = 1338;
  res[3407] = 1347;
  res[3413] = 1929;
  res[3433] = 1712;
  res[3449] = 1590;
  res[3457] = 887;
  res[3461] = 1358;
  res[3463] = 1707;
  res[3467] = 977;
  res[3469] = 1510;
  res[3491] = 1278;
  res[3499] = 1402;
  res[3511] = 1492;
  res[3517] = 1077;
  res[3527] = 965;
  res[3529] = 1525;
  res[3533] = 1614;
  res[3539] = 1438;
  res[3541] = 1307;
  res[3547] = 923;
  res[3557] = 873;
  res[3559] = 1379;
  res[3571] = 1214;
  res[3581] = 1218;
  res[3583] = 1478;
  res[3593] = 1541;
  res[3607] = 1311;
  res[3613] = 1847;
  res[3617] = 1100;
  res[3623] = 1734;
  res[3631] = 1390;
  res[3637] = 954;
  res[3643] = 1698;
  res[3659] = 1398;
  res[3671] = 1277;
  res[3673] = 1407;
  res[3677] = 892;
  res[3691] = 1281;
  res[3697] = 886;
  res[3701] = 1854;
  res[3709] = 1920;
  res[3719] = 1558;
  res[3727] = 930;
  res[3733] = 1567;
  res[3739] = 1348;
  res[3761] = 1258;
  res[3767] = 858;
  res[3769] = 1329;
  res[3779] = 1237;
  res[3793] = 1487;
  res[3797] = 819;
  res[3803] = 2172;
  res[3821] = 1474;
  res[3823] = 1636;
  res[3833] = 1579;
  res[3847] = 944;
  res[3851] = 1261;
  res[3853] = 1466;
  res[3863] = 1542;
  res[3877] = 830;
  res[3881] = 1258;
  res[3889] = 1276;
  res[3907] = 1294;
  res[3911] = 1510;
  res[3917] = 1060;
  res[3919] = 1604;
  res[3923] = 1676;
  res[3929] = 1527;
  res[3931] = 1359;
  res[3943] = 1537;
  res[3947] = 901;
  res[3967] = 902;
  res[3989] = 1289;
  res[4001] = 2834;
  res[4003] = 3351;
  res[4007] = 1962;
  res[4013] = 2762;
  res[4019] = 2459;
  res[4021] = 2103;
  res[4027] = 1452;
  res[4049] = 2183;
  res[4051] = 1852;
  res[4057] = 1286;
  res[4073] = 2091;
  res[4079] = 1951;
  res[4091] = 1792;
  res[4093] = 2320;
  res[4099] = 1984;
  res[4111] = 1847;
  res[4127] = 1185;
  res[4129] = 1852;
  res[4133] = 1922;
  res[4139] = 1713;
  res[4153] = 1853;
  res[4157] = 1029;
  res[4159] = 1594;
  res[4177] = 1015;
  res[4201] = 2110;
  res[4211] = 1647;
  res[4217] = 1180;
  res[4219] = 1836;
  res[4229] = 1686;
  res[4231] = 1524;
  res[4241] = 1457;
  res[4243] = 1777;
  res[4253] = 1755;
  res[4259] = 1541;
  res[4261] = 1472;
  res[4271] = 1377;
  res[4273] = 1573;
  res[4283] = 1630;
  res[4289] = 1462;
  res[4297] = 951;
  res[4327] = 1056;
  res[4337] = 982;
  res[4339] = 1486;
  res[4349] = 1534;
  res[4357] = 918;
  res[4363] = 1678;
  res[4373] = 1440;
  res[4391] = 1338;
  res[4397] = 919;
  res[4409] = 2171;
  res[4421] = 1455;
  res[4423] = 1801;
  res[4441] = 1376;
  res[4447] = 1002;
  res[4451] = 1318;
  res[4457] = 887;
  res[4463] = 1707;
  res[4481] = 1263;
  res[4483] = 1585;
  res[4493] = 1600;
  res[4507] = 1322;
  res[4513] = 1833;
  res[4517] = 1077;
  res[4519] = 1645;
  res[4523] = 1692;
  res[4547] = 923;
  res[4549] = 1462;
  res[4561] = 1295;
  res[4567] = 914;
  res[4583] = 1478;
  res[4591] = 1249;
  res[4597] = 852;
  res[4603] = 2263;
  res[4621] = 1496;
  res[4637] = 954;
  res[4639] = 1495;
  res[4643] = 1698;
  res[4649] = 1533;
  res[4651] = 1292;
  res[4657] = 878;
  res[4663] = 1606;
  res[4673] = 1407;
  res[4679] = 1405;
  res[4691] = 1281;
  res[4703] = 2218;
  res[4721] = 1357;
  res[4723] = 1641;
  res[4729] = 1448;
  res[4733] = 1567;
  res[4751] = 1248;
  res[4759] = 1275;
  res[4783] = 1446;
  res[4787] = 845;
  res[4789] = 1250;
  res[4793] = 1487;
  res[4799] = 1232;
  res[4801] = 1885;
  res[4813] = 1763;
  res[4817] = 1063;
  res[4831] = 1341;
  res[4861] = 1326;
  res[4871] = 1216;
  res[4877] = 830;
  res[4889] = 1276;
  res[4903] = 2153;
  res[4909] = 2004;
  res[4919] = 1604;
  res[4931] = 1359;
  res[4933] = 1563;
  res[4937] = 912;
  res[4943] = 1537;
  res[4951] = 1254;
  res[4957] = 847;
  res[4967] = 902;
  res[4969] = 1371;
  res[4973] = 1308;
  res[4987] = 813;
  res[4993] = 1532;
  res[4999] = 1331;
  res[5003] = 3351;
  res[5009] = 3030;
  res[5011] = 2194;
  res[5021] = 2103;
  res[5023] = 2564;
  res[5039] = 2121;
  res[5051] = 1852;
  res[5059] = 2064;
  res[5077] = 1245;
  res[5081] = 1793;
  res[5087] = 1279;
  res[5099] = 1984;
  res[5101] = 2315;
  res[5107] = 1567;
  res[5113] = 2169;
  res[5119] = 1921;
  res[5147] = 1170;
  res[5153] = 1853;
  res[5167] = 1102;
  res[5171] = 1497;
  res[5179] = 1581;
  res[5189] = 1630;
  res[5197] = 1017;
  res[5209] = 2273;
  res[5227] = 1090;
  res[5231] = 1524;
  res[5233] = 1856;
  res[5237] = 1050;
  res[5261] = 1472;
  res[5273] = 1573;
  res[5279] = 1486;
  res[5281] = 1383;
  res[5297] = 951;
  res[5303] = 2376;
  res[5309] = 2138;
  res[5323] = 1807;
  res[5333] = 1698;
  res[5347] = 985;
  res[5351] = 1380;
  res[5381] = 1341;
  res[5387] = 939;
  res[5393] = 1647;
  res[5399] = 1399;
  res[5407] = 1347;
  res[5413] = 1929;
  res[5417] = 1140;
  res[5419] = 1772;
  res[5431] = 1415;
  res[5437] = 985;
  res[5441] = 1376;
  res[5443] = 1706;
  res[5449] = 1590;
  res[5471] = 1286;
  res[5477] = 899;
  res[5479] = 1419;
  res[5483] = 1585;
  res[5501] = 1931;
  res[5503] = 2238;
  res[5507] = 1322;
  res[5519] = 1645;
  res[5521] = 1433;
  res[5527] = 965;
  res[5531] = 1353;
  res[5557] = 873;
  res[5563] = 1613;
  res[5569] = 1403;
  res[5573] = 1375;
  res[5581] = 1218;
  res[5591] = 1249;
  res[5623] = 1734;
  res[5639] = 1495;
  res[5641] = 1397;
  res[5647] = 1015;
  res[5651] = 1292;
  res[5653] = 1571;
  res[5657] = 878;
  res[5659] = 1398;
  res[5669] = 1431;
  res[5683] = 1541;
  res[5689] = 1389;
  res[5693] = 1566;
  res[5701] = 1854;
  res[5711] = 1476;
  res[5717] = 1054;
  res[5737] = 904;
  res[5741] = 1278;
  res[5743] = 1597;
  res[5749] = 1381;
  res[5779] = 1237;
  res[5783] = 1446;
  res[5791] = 1191;
  res[5801] = 1885;
  res[5807] = 1269;
  res[5813] = 1763;
  res[5821] = 1474;
  res[5827] = 987;
  res[5839] = 1400;
  res[5843] = 1544;
  res[5849] = 1394;
  res[5851] = 1261;
  res[5857] = 865;
  res[5861] = 1326;
  res[5867] = 867;
  res[5869] = 1380;
  res[5879] = 1271;
  res[5881] = 1258;
  res[5897] = 872;
  res[5903] = 2153;
  res[5923] = 1676;
  res[5927] = 952;
  res[5939] = 1398;
  res[5953] = 1477;
  res[5981] = 1191;
  res[5987] = 813;
  res[6007] = 1962;
  res[6011] = 2194;
  res[6029] = 2280;
  res[6037] = 1382;
  res[6043] = 2408;
  res[6047] = 1389;
  res[6053] = 2347;
  res[6067] = 1354;
  res[6073] = 2091;
  res[6079] = 1951;
  res[6089] = 1989;
  res[6091] = 1792;
  res[6101] = 2315;
  res[6113] = 2169;
  res[6121] = 1766;
  res[6131] = 1666;
  res[6133] = 1922;
  res[6143] = 1956;
  res[6151] = 1548;
  res[6163] = 1946;
  res[6173] = 1619;
  res[6197] = 1017;
  res[6199] = 1551;
  res[6203] = 2511;
  res[6211] = 1647;
  res[6217] = 1180;
  res[6221] = 1598;
  res[6229] = 1686;
  res[6247] = 1028;
  res[6257] = 984;
  res[6263] = 1811;
  res[6269] = 1587;
  res[6271] = 1377;
  res[6277] = 942;
  res[6287] = 954;
  res[6299] = 1479;
  res[6301] = 2075;
  res[6311] = 1629;
  res[6317] = 1143;
  res[6323] = 1807;
  res[6329] = 1622;
  res[6337] = 982;
  res[6343] = 1707;
  res[6353] = 1630;
  res[6359] = 1408;
  res[6361] = 1397;
  res[6367] = 971;
  res[6373] = 1440;
  res[6379] = 1374;
  res[6389] = 1387;
  res[6397] = 919;
  res[6421] = 1455;
  res[6427] = 1025;
  res[6449] = 1590;
  res[6451] = 1318;
  res[6469] = 1510;
  res[6473] = 1470;
  res[6481] = 1263;
  res[6491] = 1278;
  res[6521] = 1433;
  res[6529] = 1525;
  res[6547] = 923;
  res[6551] = 1303;
  res[6553] = 1572;
  res[6563] = 1613;
  res[6569] = 1403;
  res[6571] = 1214;
  res[6577] = 833;
  res[6581] = 1218;
  res[6599] = 1313;
  res[6607] = 1311;
  res[6619] = 1725;
  res[6637] = 954;
  res[6653] = 1571;
  res[6659] = 1398;
  res[6661] = 1327;
  res[6673] = 1407;
  res[6679] = 1405;
  res[6689] = 1389;
  res[6691] = 1281;
  res[6701] = 1854;
  res[6703] = 2218;
  res[6709] = 1920;
  res[6719] = 1558;
  res[6733] = 1567;
  res[6737] = 904;
  res[6761] = 1258;
  res[6763] = 1579;
  res[6779] = 1237;
  res[6781] = 1200;
  res[6791] = 1191;
  res[6793] = 1487;
  res[6803] = 2172;
  res[6823] = 1636;
  res[6827] = 987;
  res[6829] = 1502;
  res[6833] = 1579;
  res[6841] = 1314;
  res[6857] = 865;
  res[6863] = 1542;
  res[6869] = 1380;
  res[6871] = 1216;
  res[6883] = 1423;
  res[6899] = 1323;
  res[6907] = 1294;
  res[6911] = 1510;
  res[6917] = 1060;
  res[6947] = 901;
  res[6949] = 1414;
  res[6959] = 1338;
  res[6961] = 1286;
  res[6967] = 902;
  res[6971] = 1199;
  res[6977] = 799;
  res[6983] = 1422;
  res[6991] = 1246;
  res[6997] = 863;
  res[7001] = 2834;
  res[7013] = 2762;
  res[7019] = 2459;
  res[7027] = 1452;
  res[7039] = 2121;
  res[7043] = 2408;
  res[7057] = 1286;
  res[7069] = 2068;
  res[7079] = 1951;
  res[7103] = 2627;
  res[7109] = 2418;
  res[7121] = 1766;
  res[7127] = 1185;
  res[7129] = 1852;
  res[7151] = 1548;
  res[7159] = 1594;
  res[7177] = 1015;
  res[7187] = 1084;
  res[7193] = 1839;
  res[7207] = 1428;
  res[7211] = 1647;
  res[7213] = 2049;
  res[7219] = 1836;
  res[7229] = 1686;
  res[7237] = 1050;
  res[7243] = 1777;
  res[7247] = 1028;
  res[7253] = 1755;
  res[7283] = 1630;
  res[7297] = 951;
  res[7307] = 1412;
  res[7309] = 2138;
  res[7321] = 1541;
  res[7331] = 1449;
  res[7333] = 1698;
  res[7349] = 1534;
  res[7351] = 1380;
  res[7369] = 1468;
  res[7393] = 1647;
  res[7411] = 1562;
  res[7417] = 1140;
  res[7433] = 1712;
  res[7451] = 1318;
  res[7457] = 887;
  res[7459] = 1466;
  res[7477] = 899;
  res[7481] = 1263;
  res[7487] = 903;
  res[7489] = 1453;
  res[7499] = 1402;
  res[7507] = 1322;
  res[7517] = 1077;
  res[7523] = 1692;
  res[7529] = 1525;
  res[7537] = 917;
  res[7541] = 1307;
  res[7547] = 923;
  res[7549] = 1462;
  res[7559] = 1379;
  res[7561] = 1295;
  res[7573] = 1375;
  res[7577] = 833;
  res[7583] = 1478;
  res[7589] = 1348;
  res[7591] = 1249;
  res[7603] = 2263;
  res[7607] = 1311;
  res[7621] = 1496;
  res[7639] = 1495;
  res[7643] = 1698;
  res[7649] = 1533;
  res[7669] = 1431;
  res[7673] = 1407;
  res[7681] = 1299;
  res[7687] = 926;
  res[7691] = 1281;
  res[7699] = 1371;
  res[7703] = 2218;
  res[7717] = 1054;
  res[7723] = 1641;
  res[7727] = 930;
  res[7741] = 1278;
  res[7753] = 1515;
  res[7757] = 847;
  res[7759] = 1275;
  res[7789] = 1250;
  res[7793] = 1487;
  res[7817] = 1063;
  res[7823] = 1636;
  res[7829] = 1502;
  res[7841] = 1314;
  res[7853] = 1466;
  res[7867] = 867;
  res[7873] = 1327;
  res[7877] = 830;
  res[7879] = 1271;
  res[7883] = 1423;
  res[7901] = 1934;
  res[7907] = 1294;
  res[7919] = 1604;
  res[7927] = 952;
  res[7933] = 1563;
  res[7937] = 912;
  res[7949] = 1414;
  res[7951] = 1254;
  res[7963] = 1571;
  res[7993] = 1532;
  res[8009] = 3030;
  res[8011] = 2194;
  res[8017] = 1598;
  res[8039] = 2121;
  res[8053] = 2347;
  res[8059] = 2064;
  res[8069] = 2068;
  res[8081] = 1793;
  res[8087] = 1279;
  res[8089] = 1989;
  res[8093] = 2320;
  res[8101] = 2315;
  res[8111] = 1847;
  res[8117] = 1298;
  res[8123] = 2025;
  res[8147] = 1170;
  res[8161] = 1606;
  res[8167] = 1102;
  res[8171] = 1497;
  res[8179] = 1581;
  res[8191] = 1497;
  res[8209] = 2273;
  res[8219] = 1836;
  res[8221] = 1598;
  res[8231] = 1524;
  res[8233] = 1856;
  res[8237] = 1050;
  res[8243] = 1777;
  res[8263] = 1811;
  res[8269] = 1587;
  res[8273] = 1573;
  res[8287] = 954;
  res[8291] = 1376;
  res[8293] = 1735;
  res[8297] = 951;
  res[8311] = 1629;
  res[8317] = 1143;
  res[8329] = 1622;
  res[8353] = 1630;
  res[8363] = 1678;
  res[8369] = 1468;
  res[8377] = 903;
  res[8387] = 939;
  res[8389] = 1387;
  res[8419] = 1772;
  res[8423] = 1801;
  res[8429] = 1678;
  res[8431] = 1415;
  res[8443] = 1706;
  res[8447] = 1002;
  res[8461] = 1358;
  res[8467] = 977;
  res[8501] = 1931;
  res[8513] = 1833;
  res[8521] = 1433;
  res[8527] = 965;
  res[8537] = 917;
  res[8539] = 1438;
  res[8543] = 1589;
  res[8563] = 1613;
  res[8573] = 1375;
  res[8581] = 1218;
  res[8597] = 852;
  res[8599] = 1313;
  res[8609] = 2051;
  res[8623] = 1734;
  res[8627] = 1009;
  res[8629] = 1636;
  res[8641] = 1397;
  res[8647] = 1015;
  res[8663] = 1606;
  res[8669] = 1431;
  res[8677] = 892;
  res[8681] = 1299;
  res[8689] = 1389;
  res[8693] = 1566;
  res[8699] = 1371;
  res[8707] = 1259;
  res[8713] = 1776;
  res[8719] = 1558;
  res[8731] = 1290;
  res[8737] = 904;
  res[8741] = 1278;
  res[8747] = 926;
  res[8753] = 1515;
  res[8761] = 1258;
  res[8779] = 1237;
  res[8783] = 1446;
  res[8803] = 2172;
  res[8807] = 1269;
  res[8819] = 1600;
  res[8821] = 1474;
  res[8831] = 1341;
  res[8837] = 893;
  res[8839] = 1400;
  res[8849] = 1394;
  res[8861] = 1326;
  res[8863] = 1542;
  res[8867] = 867;
  res[8887] = 886;
  res[8893] = 1537;
  res[8923] = 1676;
  res[8929] = 1527;
  res[8933] = 1563;
  res[8941] = 1280;
  res[8951] = 1254;
  res[8963] = 1571;
  res[8969] = 1371;
  res[8971] = 1199;
  res[8999] = 1331;
  res[9001] = 2834;
  res[9007] = 1962;
  res[9011] = 2194;
  res[9013] = 2762;
  res[9029] = 2280;
  res[9041] = 1940;
  res[9043] = 2408;
  res[9049] = 2183;
  res[9059] = 2064;
  res[9067] = 1354;
  res[9091] = 1792;
  res[9103] = 2627;
  res[9109] = 2418;
  res[9127] = 1185;
  res[9133] = 1922;
  res[9137] = 1099;
  res[9151] = 1548;
  res[9157] = 1029;
  res[9161] = 1606;
  res[9173] = 1619;
  res[9181] = 1510;
  res[9187] = 1084;
  res[9199] = 1551;
  res[9203] = 2511;
  res[9209] = 2273;
  res[9221] = 1598;
  res[9227] = 1090;
  res[9239] = 1618;
  res[9241] = 1457;
  res[9257] = 984;
  res[9277] = 942;
  res[9281] = 1383;
  res[9283] = 1630;
  res[9293] = 1735;
  res[9311] = 1629;
  res[9319] = 1729;
  res[9323] = 1807;
  res[9337] = 982;
  res[9341] = 1417;
  res[9343] = 1707;
  res[9349] = 1534;
  res[9371] = 1325;
  res[9377] = 903;
  res[9391] = 1338;
  res[9397] = 919;
  res[9403] = 2341;
  res[9413] = 1929;
  res[9419] = 1772;
  res[9421] = 1455;
  res[9431] = 1415;
  res[9433] = 1712;
  res[9437] = 985;
  res[9439] = 1544;
  res[9461] = 1358;
  res[9463] = 1707;
  res[9467] = 977;
  res[9473] = 1470;
  res[9479] = 1419;
  res[9491] = 1278;
  res[9497] = 887;
  res[9511] = 1492;
  res[9521] = 1433;
  res[9533] = 1614;
  res[9539] = 1438;
  res[9547] = 923;
  res[9551] = 1303;
  res[9587] = 853;
  res[9601] = 1883;
  res[9613] = 1847;
  res[9619] = 1725;
  res[9623] = 1734;
  res[9629] = 1636;
  res[9631] = 1390;
  res[9643] = 1698;
  res[9649] = 1533;
  res[9661] = 1327;
  res[9677] = 892;
  res[9679] = 1405;
  res[9689] = 1389;
  res[9697] = 886;
  res[9719] = 1558;
  res[9721] = 1357;
  res[9733] = 1567;
  res[9739] = 1348;
  res[9743] = 1597;
  res[9749] = 1381;
  res[9767] = 858;
  res[9769] = 1329;
  res[9781] = 1200;
  res[9787] = 845;
  res[9791] = 1191;
  res[9803] = 2172;
  res[9811] = 1521;
  res[9817] = 1063;
  res[9829] = 1502;
  res[9833] = 1579;
  res[9839] = 1400;
  res[9851] = 1261;
  res[9857] = 865;
  res[9859] = 1297;
  res[9871] = 1216;
  res[9883] = 1423;
  res[9887] = 886;
  res[9901] = 1934;
  res[9907] = 1294;
  res[9923] = 1676;
  res[9929] = 1527;
  res[9931] = 1359;
  res[9941] = 1280;
  res[9949] = 1414;
  res[9967] = 902;
  res[9973] = 1308;
  res[10007] = 1607029;
  res[10009] = 1755692;
  res[10037] = 1250842;
  res[10039] = 1364989;
  res[10061] = 1393926;
  res[10067] = 1141975;
  res[10069] = 1247971;
  res[10079] = 1286779;
  res[10091] = 1397331;
  res[10093] = 1396686;
  res[10099] = 1256244;
  res[10103] = 1629683;
  res[10111] = 1371558;
  res[10133] = 1279422;
  res[10139] = 1143880;
  res[70001] = 1961753;
  res[70003] = 1958462;
  res[10009] = 1755692;
  res[30013] = 1642902;
  res[20011] = 1642544;
  res[20101] = 1634767;
  res[21001] = 1631654;
  res[10103] = 1629683;
  res[11003] = 1628066;
  res[10007] = 1607029;
  res[20021] = 1563949;
  res[20023] = 1563816;
  res[22003] = 1562355;
  res[20201] = 1557468;
  res[30203] = 1555640;
  res[50033] = 1529744;
  res[10301] = 1525636;
  res[40031] = 1524892;
  res[10303] = 1517597;
  res[13003] = 1515911;
  res[13001] = 1510566;
  res[60041] = 1475531;
  res[70019] = 1472637;
  res[50053] = 1470744;
  res[90401] = 1468633;
  res[20051] = 1468076;
  res[55001] = 1467545;
  res[30109] = 1462415;
  res[65003] = 1459996;
  res[10501] = 1459995;
}
inline void E_prime() {
  int m = (int)sqrt(N + 0.5);
  for (int i = 2; i <= m; ++i)
    if (!not_prime[i])
      for (int j = i * i; j <= N; j += i) not_prime[j] = true;
  for (int i = 2; i < N; ++i)
    if (!not_prime[i])
      for (int j = 1, k = i; j < 5; ++j) {
        k /= 10;
        P[j][k].push_back(i);
      }
}
void add(int x, int num) {
  for (int i = depth; i > 0; --i) ans[i][x] = ans[x][i] = num % 10, num /= 10;
}
void dfs(int cur) {
  if (cur > depth) {
    ++cnt;
    return;
  }
  int pre = 0;
  for (int i = 1; i < cur; ++i) pre = pre * 10 + ans[cur][i];
  for (auto i : P[depth - cur + 1][pre]) {
    add(cur, i);
    dfs(cur + 1);
  }
}
int main() {
  E_prime();
  init();
  int t;
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &num);
    if (res[num]) {
      printf("%d\n", res[num]);
      continue;
    }
    cnt = 0;
    depth = (int)(floor(log10(num)) + 0.01) + 1;
    add(1, num);
    dfs(2);
    printf("%d\n", cnt);
    res[num] = cnt;
  }
}