#include<set>
#include<map>
#include<queue>
#include<vector>
#include<algorithm>
#include<bits/stdc++.h>
#define pr pair
#define f first
#define s second
#define ll long long
#define mp make_pair
#define pll pr<ll,ll>
#define pii pr<int,int>
#define piii pr<int,pii>
using namespace std;
const ll N=30000000;
bitset<N> ip;
int pl[300005],t;
bool np[400005];
const ll at[10004]={1830561,1704256,1654839,1624694,1602748,1585989,1571241,1559918,1549840,1540941,1533150,1525813,1519922,1513269,1508559,1503386,1497828,1494129,1489905,1486417,1482526,1478941,1475577,1472301,1469133,1466295,1464711,1461223,1458478,1455327,1454218,1451883,1449393,1447612,1445029,1443285,1442268,1438511,1437688,1435603,1433623,1432638,1431158,1429158,1427934,1426191,1424449,1423146,1421898,1421628,1419519,1417646,1416274,1414828,1414474,1412536,1412147,1410149,1409474,1408847,1406619,1405863,1404699,1403820,1402802,1402215,1401459,1399972,1398687,1397968,1397392,1396025,1395311,1394081,1393614,1393702,1391745,1390950,1389856,1389245,1388381,1387557,1387087,1386285,1386089,1385355,1383659,1383030,1382174,1382128,1380556,1379940,1379988,1379181,1378300,1378033,1376974,1376282,1375646,1374445,1373813,1374365,1373705,1371926,1372058,1371582,1371125,1369670,1369265,1368783,1369027,1367263,1367593,1366673,1366702,1366010,1365671,1364879,1364544,1362945,1363457,1362875,1362218,1361711,1361693,1360505,1360075,1359812,1358772,1358371,1357694,1358070,1356999,1356325,1356153,1355675,1355408,1355562,1353893,1353699,1354154,1352893,1353318,1352067,1352363,1352427,1350570,1350629,1349811,1349988,1349551,1349068,1348598,1348290,1348074,1347463,1347326,1346979,1346537,1345534,1345467,1345052,1345037,1344148,1344250,1343870,1342750,1343627,1341701,1342348,1342590,1341617,1340993,1341109,1340809,1339785,1340136,1339101,1339554,1338378,1338430,1338644,1337533,1337215,1336825,1337694,1336942,1336732,1336451,1335763,1335333,1335015,1334358,1334184,1334013,1334197,1333039,1332828,1332728,1333379,1331699,1331602,1332094,1331299,1332331,1330909,1330905,1330083,1329115,1331016,1328913,1328286,1329117,1327735,1328125,1327505,1328134,1328727,1326656,1327992,1326545,1326422,1326355,1325013,1325946,1326145,1324507,1325030,1323676,1324471,1324039,1323312,1323704,1323564,1323644,1323318,1322412,1322577,1321553,1321056,1321652,1321010,1321127,1320778,1321423,1319222,1321325,1320082,1319841,1319252,1319323,1318620,1318164,1317751,1318243,1318227,1317120,1317923,1317654,1316880,1317728,1316729,1316254,1316539,1316206,1316451,1316551,1314933,1315186,1315672,1314329,1314160,1314095,1315458,1313856,1314612,1313608,1312902,1313818,1312227,1313064,1311658,1312590,1312101,1312261,1311683,1312156,1310767,1310478,1311086,1310712,1310005,1310242,1310182,1310407,1309376,1309144,1309310,1308904,1309238,1309602,1308011,1308449,1308473,1307365,1307459,1307365,1307944,1308069,1307477,1306979,1306086,1306183,1307096,1306236,1305504,1305369,1306168,1305262,1305380,1305858,1304665,1305587,1305253,1304242,1304083,1304355,1303813,1303183,1304066,1303145,1303168,1302996,1303669,1301890,1302393,1302421,1301760,1301898,1301509,1301611,1301088,1301827,1301599,1300825,1299953,1300767,1300446,1300130,1300096,1299358,1299137,1300774,1299335,1299928,1298231,1299663,1298662,1299617,1299348,1298974,1297079,1298133,1297889,1297848,1297077,1297916,1297096,1296659,1297883,1297111,1297236,1296834,1295677,1295805,1296135,1295894,1295462,1295466,1295501,1294529,1295579,1295266,1295380,1295623,1295528,1294885,1293798,1295047,1295194,1293221,1293731,1293532,1293187,1293245,1293806,1292926,1292517,1292209,1292952,1291949,1293219,1291874,1292302,1293038,1291684,1291289,1292072,1291483,1291409,1291011,1290750,1290740,1291215,1291223,1291076,1290190,1290683,1290516,1289129,1289274,1289262,1289652,1289629,1289015,1289724,1289032,1288642,1289432,1289117,1288916,1288330,1288181,1287895,1288189,1287831,1286863,1288046,1287647,1287709,1287457,1287224,1286607,1287372,1286426,1286531,1287147,1286347,1286195,1286285,1285564,1285956,1285815,1285896,1286309,1285277,1284275,1285978,1285467,1285398,1284254,1284242,1284156,1284574,1284397,1284688,1283530,1283503,1283361,1282662,1284297,1283568,1283569,1283341,1283148,1283435,1283320,1283295,1281521,1283446,1282490,1282664,1282496,1281999,1281511,1283014,1281161,1282422,1281367,1281093,1281359,1282077,1281265,1281127,1281367,1280385,1280103,1280756,1281516,1279422,1280298,1280005,1280307,1280707,1280630,1279928,1279541,1279120,1279288,1279228,1278457,1279255,1279417,1278581,1278467,1278794,1278700,1278867,1279112,1277707,1278529,1278287,1278186,1277895,1276769,1277637,1277871,1277789,1276550,1277119,1276914,1277064,1276670,1276492,1277253,1275978,1276992,1276588,1276292,1276248,1275540,1276029,1275689,1276400,1274945,1275367,1275164,1275548,1275587,1275191,1274598,1275513,1274754,1274794,1275197,1274616,1274640,1274253,1274871,1274327,1274318,1274237,1273943,1274077,1273918,1273254,1273595,1273498,1273923,1272170,1272624,1272899,1273644,1273082,1272527,1272348,1272765,1272901,1271754,1272225,1271522,1271748,1272517,1272519,1271437,1272185,1271598,1270643,1271312,1272215,1271548,1270516,1270955,1270537,1271375,1270886,1271228,1270929,1270368,1270587,1269933,1270902,1270445,1269476,1268744,1270447,1269503,1269836,1269852,1269420,1269563,1269233,1269759,1268750,1269119,1269846,1268784,1268059,1268821,1268876,1268731,1268557,1268357,1268221,1269127,1266786,1268111,1267500,1268439,1267169,1267795,1268755,1267130,1267561,1267835,1267148,1267532,1267548,1267867,1267315,1266842,1267244,1267580,1266461,1265773,1266818,1266443,1267174,1266086,1266247,1265666,1265166,1265413,1266249,1266058,1266284,1265744,1265906,1264470,1264818,1265670,1265376,1264658,1265253,1264717,1265645,1264053,1264500,1264800,1264849,1263636,1265124,1264323,1264784,1264289,1263645,1264071,1263657,1264117,1264560,1263568,1263440,1263507,1263903,1264011,1262966,1263130,1263353,1262561,1263523,1262464,1263035,1262356,1263802,1262783,1262266,1262794,1262115,1262776,1261717,1262724,1262145,1262411,1261757,1262347,1261853,1260979,1261871,1261305,1261882,1261204,1261535,1260853,1260618,1261653,1260964,1261648,1259834,1262353,1260922,1261175,1260159,1261678,1260233,1260281,1259802,1259170,1259930,1261157,1259752,1259568,1259688,1260211,1260060,1260016,1259120,1260189,1259096,1259390,1259876,1258545,1259381,1258152,1258331,1258551,1258682,1259289,1258886,1259207,1258447,1259371,1258074,1258583,1259221,1258448,1257892,1257696,1258586,1257399,1257415,1257570,1258245,1256997,1257953,1257248,1257699,1257145,1257231,1257270,1256846,1256765,1256394,1257950,1256273,1256694,1257039,1257116,1255842,1256427,1256417,1256701,1257170,1256678,1256900,1256131,1256125,1256762,1256481,1255382,1255789,1256180,1255060,1254675,1255577,1256435,1254919,1255984,1254417,1255495,1256331,1255617,1255103,1255131,1254573,1255735,1254708,1253918,1254773,1254073,1254478,1254824,1253737,1255083,1253327,1253785,1253266,1254963,1254481,1253848,1253159,1253166,1254711,1253498,1253758,1252495,1253663,1253468,1253583,1253609,1252664,1253331,1252903,1253946,1252962,1253744,1252425,1252441,1252394,1252416,1253534,1252516,1252538,1251601,1252811,1251309,1252298,1251940,1252078,1251737,1251817,1251889,1252518,1252387,1251379,1250612,1251917,1251569,1250826,1251459,1251768,1250743,1252066,1250864,1251461,1250799,1251406,1250857,1250535,1250803,1251028,1250978,1250691,1250480,1250182,1251179,1250782,1250614,1250389,1250480,1250682,1250150,1249738,1250014,1249856,1250705,1249769,1249903,1249999,1249680,1249361,1249300,1250322,1248484,1249298,1248347,1249475,1249617,1249683,1248994,1248812,1249187,1249293,1249618,1248045,1248822,1248792,1248339,1249247,1248431,1249451,1247689,1247944,1248281,1248289,1248686,1248384,1247662,1248659,1247864,1248315,1247329,1248150,1247972,1247236,1248292,1247433,1246677,1246644,1247017,1246892,1248231,1247126,1246860,1247804,1247426,1246504,1247306,1246806,1247058,1245956,1246595,1246421,1245797,1245924,1246245,1246908,1245581,1246207,1246791,1246829,1245999,1246094,1245507,1246956,1246624,1245371,1245603,1246659,1245521,1246374,1244616,1245733,1245756,1245595,1245420,1245242,1246057,1244853,1244926,1245448,1245313,1244383,1244760,1244429,1244834,1245246,1244054,1244719,1245410,1243960,1244282,1244887,1244411,1244868,1244171,1244012,1243419,1243653,1244263,1244275,1244125,1244587,1243859,1244820,1243730,1243713,1243469,1243160,1243841,1242749,1244135,1242579,1243618,1243357,1243772,1243856,1244015,1243342,1242884,1243094,1243390,1242692,1242624,1242528,1242680,1242152,1242705,1243249,1242226,1243195,1243046,1241877,1243317,1242751,1242502,1242414,1241681,1242991,1241261,1241950,1242988,1242040,1240671,1241082,1241973,1241275,1241471,1241829,1240827,1242256,1241250,1242424,1241604,1241499,1241496,1240562,1241453,1241431,1241651,1240714,1240563,1240794,1239997,1241590,1240317,1241216,1240712,1240082,1240724,1240592,1240617,1241305,1240000,1240482,1240325,1241321,1240115,1240109,1240359,1239997,1240328,1239239,1239429,1240317,1240064,1240687,1239618,1239635,1239789,1238861,1239250,1240236,1239667,1239560,1239017,1239645,1239134,1238819,1237962,1239307,1239162,1240190,1239407,1239207,1238290,1239750,1238731,1237924,1240124,1238618,1238930,1237841,1239143,1238412,1238404,1238009,1238712,1238551,1237040,1237991,1237478,1238122,1238933,1238113,1237554,1238135,1237615,1236853,1237587,1238094,1237686,1237237,1237462,1237010,1237414,1236636,1237557,1238076,1236528,1237388,1238303,1237115,1237255,1236517,1236643,1237122,1236967,1237113,1237378,1235807,1237852,1236803,1236510,1237377,1235618,1236849,1236991,1237262,1236254,1236508,1235778,1236942,1236611,1236242,1235875,1236789,1235838,1236046,1235776,1235548,1235658,1236107,1235725,1236680,1235750,1235375,1236836,1235056,1234614,1234745,1235597,1235718,1235871,1235680,1235252,1235378,1235214,1235398,1235093,1236069,1234664,1235235,1235207,1234917,1234702,1234795,1234809,1235269,1233954,1234833,1235848,1234943,1233624,1235109,1234013,1234369,1234476,1234818,1234249,1235473,1234786,1233988,1233919,1234473,1233579,1234588,1233979,1234317,1233693,1233308,1234161,1232511,1233032,1233536,1233059,1233793,1233981,1234188,1233144,1233330,1234443,1233556,1233724,1232658,1232867,1232793,1233018,1233318,1232244,1233219,1232961,1233350,1231970,1233181,1232721,1232434,1233459,1231962,1232624,1232370,1232875,1232304,1232649,1232514,1232626,1232697,1231361,1232184,1232057,1232175,1232068,1231730,1232401,1232210,1232304,1231759,1232564,1231195,1232358,1230755,1232378,1231697,1231446,1231655,1231582,1231442,1233104,1231300,1231562,1232051,1230418,1232047,1231751,1230937,1231407,1230626,1230184,1230799,1230875,1230691,1231445,1230325,1230710,1231447,1230849,1230424,1231084,1230184,1230009,1230936,1229832,1230624,1230519,1229824,1229692,1229308,1230983,1230604,1231262,1230416,1230268,1230621,1229608,1228302,1230249,1229600,1229532,1230071,1230074,1229660,1229365,1229774,1230246,1229653,1230435,1228426,1228549,1229046,1228840,1230607,1229884,1228581,1229716,1229188,1229953,1229353,1229009,1229612,1229331,1229085,1228418,1229440,1228880,1228223,1228129,1228871,1228889,1227925,1228455,1228716,1228790,1229148,1229321,1228532,1228210,1228272,1229049,1228313,1227482,1228445,1230192,1228601,1227670,1227637,1227661,1228310,1227857,1228036,1228572,1228686,1227615,1227034,1227683,1228778,1226667,1227936,1227852,1226464,1226507,1227225,1227563,1226125,1227585,1228312,1226688,1228117,1227581,1227020,1227230,1227027,1227275,1227304,1227010,1227123,1227947,1226922,1227547,1226220,1226304,1226181,1227314,1227198,1226936,1227092,1226476,1226960,1226664,1225933,1226291,1227365,1226073,1226668,1226628,1226463,1226820,1226384,1225855,1226461,1226284,1226051,1225942,1225942,1226989,1225803,1226383,1225879,1225326,1226714,1226385,1224923,1224737,1226051,1225750,1225384,1224664,1224491,1225270,1225538,1225093,1226252,1225326,1224853,1223551,1225687,1225508,1225329,1225006,1224676,1225085,1224726,1224755,1224780,1225878,1224683,1224351,1224793,1225212,1225173,1224197,1224743,1224921,1224318,1224684,1224521,1224976,1224697,1224682,1224132,1225066,1224644,1224780,1223869,1224800,1223622,1223812,1224659,1224224,1223671,1222955,1225679,1223594,1223864,1224248,1224364,1223931,1223925,1223619,1223014,1223579,1223519,1223820,1223492,1223947,1223333,1224269,1222814,1223879,1223762,1223151,1223584,1222762,1224007,1223165,1224453,1222748,1222735,1222545,1223697,1223953,1222040,1223707,1223851,1222966,1222913,1222079,1222998,1222603,1222433,1222744,1222974,1222235,1222496,1222792,1222384,1222239,1221684,1222473,1222123,1223562,1221697,1223008,1222010,1222832,1221979,1222293,1222331,1223118,1222222,1221320,1222785,1221930,1221522,1221986,1222127,1221112,1221250,1221188,1221232,1222263,1221604,1221266,1221226,1221931,1220689,1221683,1221011,1221444,1222210,1221701,1221696,1221593,1221826,1220352,1221944,1221717,1220700,1221436,1220103,1221471,1220741,1222037,1221186,1220484,1221914,1220408,1220850,1220855,1220323,1219441,1220320,1220774,1220233,1220981,1220586,1219828,1220939,1221354,1220928,1220166,1220438,1220156,1220195,1219469,1220676,1221455,1219715,1219703,1220168,1219470,1220689,1219715,1219791,1219774,1220298,1220596,1219484,1220386,1219785,1220518,1219839,1219733,1218950,1219751,1219203,1219110,1219773,1219506,1219306,1219319,1219587,1219526,1218480,1219443,1219309,1219067,1220077,1219502,1219215,1218870,1219391,1218432,1218701,1219595,1219220,1218927,1218627,1219416,1219324,1218715,1219321,1219172,1218794,1219467,1218696,1218976,1217903,1218377,1218437,1219915,1218750,1219285,1217778,1219163,1217238,1219871,1218475,1217321,1217580,1218981,1217802,1217794,1219195,1218564,1217195,1218099,1217492,1217495,1218399,1217317,1218036,1217387,1219204,1217531,1218271,1217935,1218710,1218729,1216385,1216565,1217047,1217113,1217803,1217221,1217004,1217220,1218600,1217655,1218811,1217118,1217726,1216969,1217216,1217186,1217776,1217908,1217011,1217252,1217475,1217664,1217271,1216613,1217081,1217599,1216931,1216859,1216819,1216375,1217498,1216709,1216723,1218131,1216402,1217125,1216409,1216402,1217232,1216730,1216663,1216867,1215536,1216614,1216073,1216374,1215421,1216119,1217830,1215690,1216528,1216297,1216468,1216877,1216765,1215951,1216508,1216532,1215738,1216545,1215717,1215957,1215965,1214885,1216049,1217386,1215520,1216121,1214449,1216175,1214500,1215714,1214835,1215666,1215389,1214499,1215816,1215680,1216152,1215640,1215017,1214790,1215963,1216185,1216055,1215302,1215814,1214567,1215456,1215375,1214993,1215523,1215390,1214198,1214746,1215273,1214078,1215391,1214542,1214805,1216173,1214447,1215278,1215170,1214689,1214268,1214899,1215323,1215841,1214182,1215433,1214183,1214960,1214197,1214831,1214513,1214543,1214156,1213660,1214501,1213850,1214825,1214987,1214233,1213545,1213043,1214599,1214566,1213663,1213872,1214436,1214567,1213031,1213548,1213452,1214503,1214358,1212696,1214098,1213563,1213522,1214006,1214224,1213979,1214672,1213979,1214666,1213106,1212560,1213002,1213195,1213199,1213515,1212983,1213493,1213658,1212757,1214170,1213440,1213843,1212963,1213322,1213241,1213413,1213651,1213863,1213640,1212693,1213281,1212372,1212456,1212584,1212835,1211907,1213296,1213157,1212624,1212332,1212610,1212953,1212442,1213514,1212418,1212966,1212229,1212831,1212715,1212412,1212030,1212148,1213282,1212200,1211717,1211358,1213047,1213041,1212534,1212489,1212089,1212217,1212028,1211429,1212923,1211757,1211931,1213118,1211789,1211513,1211908,1211192,1212523,1212044,1212593,1211893,1211107,1212518,1211523,1210941,1211078,1210792,1212864,1211749,1211357,1211556,1211946,1211586,1211745,1211048,1211102,1210749,1211419,1211709,1212161,1210369,1211894,1210632,1210925,1212014,1210960,1211733,1211345,1211875,1210633,1210910,1210728,1209057,1211161,1211744,1210432,1210639,1211294,1210553,1211542,1211603,1211338,1210549,1210845,1210090,1210105,1210895,1210884,1209669,1210156,1210542,1211133,1209793,1210736,1210697,1210165,1211081,1210366,1210374,1209943,1210187,1210315,1209899,1211009,1209672,1210416,1209704,1209887,1208723,1209636,1209098,1209916,1209780,1210069,1209504,1211024,1209834,1210404,1209870,1210251,1209132,1209104,1209695,1209633,1209816,1209883,1210488,1209325,1208573,1210221,1210328,1209609,1209409,1208850,1209537,1209664,1209746,1210022,1209232,1208959,1208897,1209562,1209506,1209500,1209379,1209367,1208081,1209187,1208499,1208984,1209208,1209679,1208146,1209029,1209133,1207707,1210029,1209019,1209307,1209181,1208253,1208245,1209550,1209264,1208645,1208954,1208732,1208589,1209003,1209274,1208019,1209003,1208762,1208474,1207896,1208758,1208580,1208610,1207994,1208468,1207990,1208406,1208004,1208355,1207654,1209024,1208079,1208737,1207702,1208823,1206723,1207931,1208167,1208222,1207427,1207717,1208760,1207458,1207555,1208480,1206957,1208191,1207537,1208123,1207123,1206888,1207646,1207502,1207836,1207684,1207505,1207290,1208171,1206115,1207711,1208443,1207261,1207228,1207110,1207859,1207369,1206664,1207271,1207466,1207353,1207603,1207225,1207411,1207641,1206437,1206123,1207111,1207809,1207379,1207719,1207096,1207087,1207057,1207063,1206157,1206314,1206936,1206394,1206188,1206326,1206805,1207420,1206960,1205992,1207628,1206762,1206930,1206765,1206069,1206697,1206701,1205782,1207104,1207800,1206521,1206996,1205529,1206147,1206882,1205555,1206125,1206268,1206600,1205475,1205710,1206641,1205882,1206103,1206168,1206547,1206052,1205772,1206095,1206334,1206274,1206306,1206650,1205654,1205657,1205380,1207214,1205174,1205805,1205892,1205481,1204888,1205883,1205790,1205717,1206208,1206377,1205538,1205543,1206073,1205299,1205265,1205870,1205327,1205750,1204672,1205295,1205759,1205569,1204793,1204975,1204275,1204839,1205536,1204789,1204894,1205522,1204666,1205536,1205748,1204702,1204936,1205215,1204363,1205797,1204525,1205036,1205409,1204475,1205537,1204991,1204990,1205164,1205267,1204472,1204850,1203819,1205376,1205066,1204360,1205250,1205843,1204048,1204171,1203869,1203771,1205591,1203355,1204358,1205279,1204312,1203809,1203473,1203617,1205042,1204844,1203847,1204500,1203621,1204052,1204233,1204462,1203087,1204776,1203993,1204070,1205298,1204357,1204419,1203524,1204108,1203582,1205218,1203747,1203139,1203321,1203421,1204423,1203974,1203975,1203519,1204093,1203526,1202787,1203842,1203070,1204322,1203232,1202895,1203578,1204408,1202498,1204062,1203361,1202707,1203215,1203371,1203841,1204177,1202764,1203438,1202660,1204000,1202627,1203170,1203402,1203150,1203058,1202262,1204018,1203528,1203436,1203395,1202544,1203706,1202928,1202927,1203476,1202810,1203608,1201457,1203450,1201689,1203566,1203560,1203327,1201407,1202514,1202253,1202977,1201781,1203190,1202268,1202589,1202870,1203564,1202750,1202738,1202822,1203188,1202245,1202675,1202385,1202265,1201508,1202886,1202807,1202749,1202131,1202563,1202946,1201204,1202410,1202427,1202100,1202055,1202071,1202206,1202087,1202282,1203330,1202355,1202955,1201446,1201626,1201541,1202052,1201735,1202608,1201058,1201647,1202745,1201436,1202565,1200924,1201652,1201531,1202083,1201657,1201338,1201736,1203152,1202036,1201233,1202615,1201536,1200762,1200939,1201639,1201204,1201987,1201032,1201183,1201550,1201126,1201358,1200799,1200865,1201834,1200859,1200511,1201240,1200969,1200937,1200803,1201557,1200925,1201334,1201554,1200763,1201555,1200492,1200400,1201118,1200966,1200424,1201625,1200650,1200571,1200904,1201014,1200353,1201397,1199769,1200771,1200960,1199992,1202083,1201481,1201135,1200588,1201438,1200953,1201094,1199811,1200472,1200610,1201098,1201115,1200838,1200597,1200577,1201133,1200765,1198813,1199656,1200563,1199385,1200361,1199138,1201014,1199828,1200112,1199155,1199111,1200139,1200345,1199520,1199351,1199847,1199414,1199735,1199710,1199612,1200273,1200181,1200209,1199677,1199678,1199669,1200853,1200586,1199457,1199546,1199937,1198991,1198826,1199808,1200750,1200051,1199871,1199438,1199440,1199039,1199935,1198946,1199631,1199803,1199322,1199454,1199346,1199323,1199284,1199257,1199810,1199479,1199125,1199975,1199798,1199040,1199264,1199763,1199467,1198668,1198405,1199786,1199235,1199960,1198501,1198458,1198938,1198376,1199024,1199138,1198995,1198377,1199011,1198441,1199879,1198024,1198700,1198323,1199037,1197871,1197831,1198138,1198600,1198812,1198547,1198887,1198720,1198999,1197527,1199392,1198383,1198733,1198826,1198947,1197856,1199191,1199021,1197668,1197235,1200115,1198553,1198412,1197764,1198005,1198746,1198079,1198438,1198221,1198375,1197833,1198443,1197676,1198114,1198551,1197996,1198275,1197216,1198807,1198149,1198541,1197312,1197980,1197586,1197668,1198241,1198281,1197587,1198333,1197090,1199027,1197550,1197182,1198293,1197513,1198246,1197707,1197962,1198152,1197367,1198029,1197720,1197312,1196777,1196432,1198296,1197337,1197446,1197393,1198276,1197537,1197441,1197080,1197624,1197459,1196919,1198098,1196739,1196250,1197718,1198549,1196374,1197661,1197051,1197330,1197425,1198309,1197467,1197675,1196618,1197879,1197247,1197241,1196875,1196729,1198030,1195857,1196229,1196883,1197280,1198432,1196888,1195397,1196811,1197287,1196890,1196076,1197799,1196801,1196517,1197117,1196704,1197275,1196330,1195881,1196516,1196533,1196735,1196254,1196002,1196877,1197040,1196217,1196089,1196328,1196820,1195620,1196911,1195797,1195358,1196139,1195537,1196389,1196162,1195779,1195556,1195966,1196045,1196663,1196387,1195553,1196083,1195711,1196739,1195781,1196868,1195673,1195525,1195832,1196871,1196424,1194923,1196598,1196110,1195843,1195401,1195628,1196187,1195703,1196563,1196281,1195515,1194792,1196272,1195723,1195723,1196089,1195256,1195561,1196557,1195982,1195762,1195573,1196333,1195823,1195439,1194277,1195594,1194909,1195596,1194535,1195287,1196406,1194717,1196300,1194865,1194481,1195046,1196018,1194701,1194876,1195131,1195418,1194711,1195330,1194176,1195646,1195304,1195589,1195546,1194628,1194579,1194037,1194940,1195797,1194854,1194173,1195537,1194213,1194960,1194211,1195273,1195017,1195525,1194665,1194901,1194890,1194660,1194945,1194812,1194878,1194924,1194115,1194602,1193998,1194412,1196044,1193651,1194849,1194171,1194378,1193468,1194120,1194410,1194709,1194977,1194120,1194079,1194868,1194823,1193581,1194415,1195451,1194222,1193607,1194495,1194606,1194027,1193799,1194166,1194140,1193938,1194806,1194057,1193892,1193167,1194030,1193709,1193756,1194040,1194257,1194156,1194159,1194783,1193710,1193721,1193230,1193445,1194140,1193817,1194314,1193317,1192592,1194209,1194101,1194942,1192527,1193930,1193946,1194336,1193163,1193779,1194174,1193364,1193717,1192497,1193354,1194191,1194110,1193412,1193082,1194279,1193799,1192255,1193677,1192828,1194445,1193343,1192584,1193572,1193084,1192881,1192631,1194102,1193742,1192886,1192808,1192418,1193284,1193095,1192871,1192365,1194078,1193117,1193481,1193570,1193676,1192886,1193379,1193144,1193686,1193534,1192946,1192125,1192863,1193134,1192400,1193428,1192669,1192676,1191367,1192371,1193493,1192267,1194227,1192286,1192253,1192546,1191754,1193606,1192492,1192771,1191439,1192469,1192166,1192357,1192091,1192604,1191941,1191956,1193785,1192654,1192566,1192984,1192349,1193407,1192181,1192832,1192593,1192070,1191158,1191789,1192984,1192566,1192457,1192528,1191125,1191955,1192980,1192024,1191486,1192168,1192208,1192464,1191298,1191438,1192094,1192726,1192261,1192773,1191365,1192398,1191647,1192196,1192161,1191360,1190770,1191115,1191288,1191955,1191805,1191171,1192460,1192578,1191987,1191776,1191656,1191403,1191342,1192168,1192004,1191490,1191491,1191942,1191812,1191991,1191023,1190801,1191254,1191767,1191254,1190729,1190754,1189865,1191872,1190973,1191076,1190707,1192149,1191779,1191104,1190655,1191669,1190470,1191459,1191144,1190418,1190871,1191591,1191269,1191530,1191703,1190837,1191011,1191047,1191536,1190515,1191954,1190522,1191866,1190672,1190969,1191296,1191130,1191627,1190253,1191278,1191011,1190533,1191062,1191233,1189938,1190293,1190759,1190208,1190652,1190600,1191619,1189949,1191318,1191763,1190505,1190144,1190685,1190020,1189741,1190044,1189754,1190586,1190356,1190259,1190912,1190684,1190731,1188981,1189664,1190661,1191000,1190770,1189612,1190986,1190148,1191165,1189633,1190197,1190451,1191244,1189478,1190139,1190209,1190443,1190315,1190041,1190941,1189656,1189472,1190698,1189233,1190930,1188332,1190499,1191127,1189242,1189798,1190214,1189589,1190717,1190804,1189662,1189160,1189058,1189738,1189950,1189594,1189425,1189689,1190450,1190124,1189480,1190860,1189989,1189914,1188675,1190087,1189229,1189295,1188925,1189070,1189781,1189618,1189992,1188634,1189282,1188620,1189963,1188468,1188839,1189526,1189671,1189649,1189165,1188992,1189387,1189143,1189299,1189488,1189439,1189807,1189179,1189347,1189001,1189543,1188336,1190050,1188680,1189891,1188879,1188624,1189009,1189945,1188928,1188453,1189271,1188442,1189375,1189138,1189446,1189040,1188290,1187861,1189033,1188947,1188235,1189168,1189191,1188511,1189089,1188289,1189123,1189287,1188835,1189005,1188184,1189364,1187655,1189289,1189570,1189445,1186882,1188330,1188422,1188777,1188094,1188529,1189834,1188171,1189200,1187870,1188337,1187838,1188276,1188915,1188054,1188389,1189064,1188067,1187958,1188473,1189024,1188850,1188563,1187939,1188007,1187578,1188375,1188856,1188864,1188783,1188554,1187284,1186937,1188440,1188398,1187576,1188139,1188081,1188181,1186986,1187378,1187896,1188044,1186476,1187670,1187814,1188750,1188367,1187959,1188521,1188089,1187536,1187760,1187214,1187578,1188399,1186821,1188601,1188064,1187682,1187499,1188523,1187833,1187310,1188438,1187637,1187559,1186520,1188351,1187904,1187767,1187277,1187081,1188641,1187208,1187453,1188523,1187075,1188483,1186607,1186832,1187835,1187409,1187474,1187250,1187158,1188397,1187042,1186497,1187493,1186923,1187311,1187086,1186979,1186931,1187465,1187142,1186752,1186464,1187401,1187089,1186800,1186694,1187313,1187507,1187281,1186463,1186375,1187472,1186311,1187076,1187007,1186600,1186137,1188039,1186934,1187046,1186884,1187627,1186899,1186762,1185665,1187380,1186633,1186253,1186366,1185447,1186745,1187089,1186099,1187163,1186660,1186920,1186818,1186953,1186591,1185831,1186470,1187526,1185881,1186272,1186665,1186821,1186201,1186912,1186562,1186442,1186360,1186564,1186931,1186363,1185632,1187084,1186098,1187157,1185612,1185915,1185353,1186626,1186258,1185915,1185692,1185669,1186676,1185526,1186238,1186845,1186030,1185907,1185431,1185989,1184761,1185977,1186107,1185603,1186157,1186381,1185534,1185995,1185926,1186304,1186790,1185738,1185888,1185551,1185984,1186191,1186048,1185836,1185736,1186101,1185369,1185155,1185858,1186341,1185522,1185093,1185574,1185665,1185596,1186084,1185343,1185811,1185536,1186039,1185180,1185244,1186099,1185435,1186079,1184832,1186254,1185370,1186121,1185358,1186026,1185097,1185631,1186129,1185986,1185477,1185660,1184689,1185795,1185890,1184440,1185123,1184551,1185070,1184808,1185770,1184266,1185796,1185694,1185134,1185310,1184835,1185584,1184422,1184582,1184981,1184860,1185191,1185108,1184663,1184901,1184699,1185469,1185075,1184928,1183930,1184440,1184527,1184397,1184366,1185970,1184640,1184713,1184792,1185855,1185137,1184469,1185388,1184040,1184635,1184452,1185282,1185227,1184526,1183491,1184188,1184490,1184026,1184875,1184547,1184062,1184586,1184557,1184410,1184793,1185043,1184415,1184842,394921};
ll pf(ll n)
{
	if(n==0) return 0;
	int g=(n-1)/N;
	ll fd=g*N+1;
	int r=(n-1)%N;
	ll rt=-1;
	for(int i=0;i<g;i++) rt+=at[i];
	ip.set();
	for(int j=0;j<t;j++)
	{
		int k=pl[j];
		if(k<=n) rt++;
		int st=k-1-(fd-1)%k;
		for(;st<N;st+=k) ip.reset(st);
	}
	for(int i=0;i<=r;i++) if(ip[i]) rt++;
	return rt;
}
void sl()
{
	ll n;
	cin>>n;
	ll g=pf(n);
	ll h=pf(n/2);
	cerr<<"G "<<g<<' '<<h<<endl;
	ll r=n-g+h-1;
	cout<<n-r/2<<endl;
}
int main()
{
	for(int i=2;i<316300;i++)
	{
		if(np[i]) continue;
		pl[t++]=i;
		for(int j=i*2;j<316300;j+=i) np[j]=1;
	}
	int t;
	cin>>t;
	while(t--) sl();
	return 0;
}