#include <stdio.h>
#include <math.h>
FILE *g,*h;
unsigned int a[5000];long r,o,n,b[31],c[31],d[31],e[31],f[31],l,i,j,min,k,q;
int main()
{a[0]=2;a[1]=3;a[2]=5;a[3]=7;a[4]=11;a[5]=13;a[6]=17;a[7]=19;a[8]=23;a[9]=29;a[10]=31;
a[11]=37;a[12]=41;a[13]=43;a[14]=47;a[15]=53;a[16]=59;a[17]=61;a[18]=67;a[19]=71;a[20]=73;
a[21]=79;a[22]=83;a[23]=89;a[24]=97;a[25]=101;a[26]=103;a[27]=107;a[28]=109;a[29]=113;a[30]=127;
a[31]=131;a[32]=137;a[33]=139;a[34]=149;a[35]=151;a[36]=157;a[37]=163;a[38]=167;a[39]=173;a[40]=179;
a[41]=181;a[42]=191;a[43]=193;a[44]=197;a[45]=199;a[46]=211;a[47]=223;a[48]=227;a[49]=229;a[50]=233;
a[51]=239;a[52]=241;a[53]=251;a[54]=257;a[55]=263;a[56]=269;a[57]=271;a[58]=277;a[59]=281;a[60]=283;
a[61]=293;a[62]=307;a[63]=311;a[64]=313;a[65]=317;a[66]=331;a[67]=337;a[68]=347;a[69]=349;a[70]=353;
a[71]=359;a[72]=367;a[73]=373;a[74]=379;a[75]=383;a[76]=389;a[77]=397;a[78]=401;a[79]=409;a[80]=419;
a[81]=421;a[82]=431;a[83]=433;a[84]=439;a[85]=443;a[86]=449;a[87]=457;a[88]=461;a[89]=463;a[90]=467;
a[91]=479;a[92]=487;a[93]=491;a[94]=499;a[95]=503;a[96]=509;a[97]=521;a[98]=523;a[99]=541;a[100]=547;
a[101]=557;a[102]=563;a[103]=569;a[104]=571;a[105]=577;a[106]=587;a[107]=593;a[108]=599;a[109]=601;a[110]=607;
a[111]=613;a[112]=617;a[113]=619;a[114]=631;a[115]=641;a[116]=643;a[117]=647;a[118]=653;a[119]=659;a[120]=661;
a[121]=673;a[122]=677;a[123]=683;a[124]=691;a[125]=701;a[126]=709;a[127]=719;a[128]=727;a[129]=733;a[130]=739;
a[131]=743;a[132]=751;a[133]=757;a[134]=761;a[135]=769;a[136]=773;a[137]=787;a[138]=797;a[139]=809;a[140]=811;
a[141]=821;a[142]=823;a[143]=827;a[144]=829;a[145]=839;a[146]=853;a[147]=857;a[148]=859;a[149]=863;a[150]=877;
a[151]=881;a[152]=883;a[153]=887;a[154]=907;a[155]=911;a[156]=919;a[157]=929;a[158]=937;a[159]=941;a[160]=947;
a[161]=953;a[162]=967;a[163]=971;a[164]=977;a[165]=983;a[166]=991;a[167]=997;a[168]=1009;a[169]=1013;a[170]=1019;
a[171]=1021;a[172]=1031;a[173]=1033;a[174]=1039;a[175]=1049;a[176]=1051;a[177]=1061;a[178]=1063;a[179]=1069;a[180]=1087;
a[181]=1091;a[182]=1093;a[183]=1097;a[184]=1103;a[185]=1109;a[186]=1117;a[187]=1123;a[188]=1129;a[189]=1151;a[190]=1153;
a[191]=1163;a[192]=1171;a[193]=1181;a[194]=1187;a[195]=1193;a[196]=1201;a[197]=1213;a[198]=1217;a[199]=1223;a[200]=1229;
a[201]=1231;a[202]=1237;a[203]=1249;a[204]=1259;a[205]=1277;a[206]=1279;a[207]=1283;a[208]=1289;a[209]=1291;a[210]=1297;
a[211]=1301;a[212]=1303;a[213]=1307;a[214]=1319;a[215]=1321;a[216]=1327;a[217]=1361;a[218]=1367;a[219]=1373;a[220]=1381;
a[221]=1399;a[222]=1409;a[223]=1423;a[224]=1427;a[225]=1429;a[226]=1433;a[227]=1439;a[228]=1447;a[229]=1451;a[230]=1453;
a[231]=1459;a[232]=1471;a[233]=1481;a[234]=1483;a[235]=1487;a[236]=1489;a[237]=1493;a[238]=1499;a[239]=1511;a[240]=1523;
a[241]=1531;a[242]=1543;a[243]=1549;a[244]=1553;a[245]=1559;a[246]=1567;a[247]=1571;a[248]=1579;a[249]=1583;a[250]=1597;
a[251]=1601;a[252]=1607;a[253]=1609;a[254]=1613;a[255]=1619;a[256]=1621;a[257]=1627;a[258]=1637;a[259]=1657;a[260]=1663;
a[261]=1667;a[262]=1669;a[263]=1693;a[264]=1697;a[265]=1699;a[266]=1709;a[267]=1721;a[268]=1723;a[269]=1733;a[270]=1741;
a[271]=1747;a[272]=1753;a[273]=1759;a[274]=1777;a[275]=1783;a[276]=1787;a[277]=1789;a[278]=1801;a[279]=1811;a[280]=1823;
a[281]=1831;a[282]=1847;a[283]=1861;a[284]=1867;a[285]=1871;a[286]=1873;a[287]=1877;a[288]=1879;a[289]=1889;a[290]=1901;
a[291]=1907;a[292]=1913;a[293]=1931;a[294]=1933;a[295]=1949;a[296]=1951;a[297]=1973;a[298]=1979;a[299]=1987;a[300]=1993;
a[301]=1997;a[302]=1999;a[303]=2003;a[304]=2011;a[305]=2017;a[306]=2027;a[307]=2029;a[308]=2039;a[309]=2053;a[310]=2063;
a[311]=2069;a[312]=2081;a[313]=2083;a[314]=2087;a[315]=2089;a[316]=2099;a[317]=2111;a[318]=2113;a[319]=2129;a[320]=2131;
a[321]=2137;a[322]=2141;a[323]=2143;a[324]=2153;a[325]=2161;a[326]=2179;a[327]=2203;a[328]=2207;a[329]=2213;a[330]=2221;
a[331]=2237;a[332]=2239;a[333]=2243;a[334]=2251;a[335]=2267;a[336]=2269;a[337]=2273;a[338]=2281;a[339]=2287;a[340]=2293;
a[341]=2297;a[342]=2309;a[343]=2311;a[344]=2333;a[345]=2339;a[346]=2341;a[347]=2347;a[348]=2351;a[349]=2357;a[350]=2371;
a[351]=2377;a[352]=2381;a[353]=2383;a[354]=2389;a[355]=2393;a[356]=2399;a[357]=2411;a[358]=2417;a[359]=2423;a[360]=2437;
a[361]=2441;a[362]=2447;a[363]=2459;a[364]=2467;a[365]=2473;a[366]=2477;a[367]=2503;a[368]=2521;a[369]=2531;a[370]=2539;
a[371]=2543;a[372]=2549;a[373]=2551;a[374]=2557;a[375]=2579;a[376]=2591;a[377]=2593;a[378]=2609;a[379]=2617;a[380]=2621;
a[381]=2633;a[382]=2647;a[383]=2657;a[384]=2659;a[385]=2663;a[386]=2671;a[387]=2677;a[388]=2683;a[389]=2687;a[390]=2689;
a[391]=2693;a[392]=2699;a[393]=2707;a[394]=2711;a[395]=2713;a[396]=2719;a[397]=2729;a[398]=2731;a[399]=2741;a[400]=2749;
a[401]=2753;a[402]=2767;a[403]=2777;a[404]=2789;a[405]=2791;a[406]=2797;a[407]=2801;a[408]=2803;a[409]=2819;a[410]=2833;
a[411]=2837;a[412]=2843;a[413]=2851;a[414]=2857;a[415]=2861;a[416]=2879;a[417]=2887;a[418]=2897;a[419]=2903;a[420]=2909;
a[421]=2917;a[422]=2927;a[423]=2939;a[424]=2953;a[425]=2957;a[426]=2963;a[427]=2969;a[428]=2971;a[429]=2999;a[430]=3001;
a[431]=3011;a[432]=3019;a[433]=3023;a[434]=3037;a[435]=3041;a[436]=3049;a[437]=3061;a[438]=3067;a[439]=3079;a[440]=3083;
a[441]=3089;a[442]=3109;a[443]=3119;a[444]=3121;a[445]=3137;a[446]=3163;a[447]=3167;a[448]=3169;a[449]=3181;a[450]=3187;
a[451]=3191;a[452]=3203;a[453]=3209;a[454]=3217;a[455]=3221;a[456]=3229;a[457]=3251;a[458]=3253;a[459]=3257;a[460]=3259;
a[461]=3271;a[462]=3299;a[463]=3301;a[464]=3307;a[465]=3313;a[466]=3319;a[467]=3323;a[468]=3329;a[469]=3331;a[470]=3343;
a[471]=3347;a[472]=3359;a[473]=3361;a[474]=3371;a[475]=3373;a[476]=3389;a[477]=3391;a[478]=3407;a[479]=3413;a[480]=3433;
a[481]=3449;a[482]=3457;a[483]=3461;a[484]=3463;a[485]=3467;a[486]=3469;a[487]=3491;a[488]=3499;a[489]=3511;a[490]=3517;
a[491]=3527;a[492]=3529;a[493]=3533;a[494]=3539;a[495]=3541;a[496]=3547;a[497]=3557;a[498]=3559;a[499]=3571;a[500]=3581;
a[501]=3583;a[502]=3593;a[503]=3607;a[504]=3613;a[505]=3617;a[506]=3623;a[507]=3631;a[508]=3637;a[509]=3643;a[510]=3659;
a[511]=3671;a[512]=3673;a[513]=3677;a[514]=3691;a[515]=3697;a[516]=3701;a[517]=3709;a[518]=3719;a[519]=3727;a[520]=3733;
a[521]=3739;a[522]=3761;a[523]=3767;a[524]=3769;a[525]=3779;a[526]=3793;a[527]=3797;a[528]=3803;a[529]=3821;a[530]=3823;
a[531]=3833;a[532]=3847;a[533]=3851;a[534]=3853;a[535]=3863;a[536]=3877;a[537]=3881;a[538]=3889;a[539]=3907;a[540]=3911;
a[541]=3917;a[542]=3919;a[543]=3923;a[544]=3929;a[545]=3931;a[546]=3943;a[547]=3947;a[548]=3967;a[549]=3989;a[550]=4001;
a[551]=4003;a[552]=4007;a[553]=4013;a[554]=4019;a[555]=4021;a[556]=4027;a[557]=4049;a[558]=4051;a[559]=4057;a[560]=4073;
a[561]=4079;a[562]=4091;a[563]=4093;a[564]=4099;a[565]=4111;a[566]=4127;a[567]=4129;a[568]=4133;a[569]=4139;a[570]=4153;
a[571]=4157;a[572]=4159;a[573]=4177;a[574]=4201;a[575]=4211;a[576]=4217;a[577]=4219;a[578]=4229;a[579]=4231;a[580]=4241;
a[581]=4243;a[582]=4253;a[583]=4259;a[584]=4261;a[585]=4271;a[586]=4273;a[587]=4283;a[588]=4289;a[589]=4297;a[590]=4327;
a[591]=4337;a[592]=4339;a[593]=4349;a[594]=4357;a[595]=4363;a[596]=4373;a[597]=4391;a[598]=4397;a[599]=4409;a[600]=4421;
a[601]=4423;a[602]=4441;a[603]=4447;a[604]=4451;a[605]=4457;a[606]=4463;a[607]=4481;a[608]=4483;a[609]=4493;a[610]=4507;
a[611]=4513;a[612]=4517;a[613]=4519;a[614]=4523;a[615]=4547;a[616]=4549;a[617]=4561;a[618]=4567;a[619]=4583;a[620]=4591;
a[621]=4597;a[622]=4603;a[623]=4621;a[624]=4637;a[625]=4639;a[626]=4643;a[627]=4649;a[628]=4651;a[629]=4657;a[630]=4663;
a[631]=4673;a[632]=4679;a[633]=4691;a[634]=4703;a[635]=4721;a[636]=4723;a[637]=4729;a[638]=4733;a[639]=4751;a[640]=4759;
a[641]=4783;a[642]=4787;a[643]=4789;a[644]=4793;a[645]=4799;a[646]=4801;a[647]=4813;a[648]=4817;a[649]=4831;a[650]=4861;
a[651]=4871;a[652]=4877;a[653]=4889;a[654]=4903;a[655]=4909;a[656]=4919;a[657]=4931;a[658]=4933;a[659]=4937;a[660]=4943;
a[661]=4951;a[662]=4957;a[663]=4967;a[664]=4969;a[665]=4973;a[666]=4987;a[667]=4993;a[668]=4999;a[669]=5003;a[670]=5009;
a[671]=5011;a[672]=5021;a[673]=5023;a[674]=5039;a[675]=5051;a[676]=5059;a[677]=5077;a[678]=5081;a[679]=5087;a[680]=5099;
a[681]=5101;a[682]=5107;a[683]=5113;a[684]=5119;a[685]=5147;a[686]=5153;a[687]=5167;a[688]=5171;a[689]=5179;a[690]=5189;
a[691]=5197;a[692]=5209;a[693]=5227;a[694]=5231;a[695]=5233;a[696]=5237;a[697]=5261;a[698]=5273;a[699]=5279;a[700]=5281;
a[701]=5297;a[702]=5303;a[703]=5309;a[704]=5323;a[705]=5333;a[706]=5347;a[707]=5351;a[708]=5381;a[709]=5387;a[710]=5393;
a[711]=5399;a[712]=5407;a[713]=5413;a[714]=5417;a[715]=5419;a[716]=5431;a[717]=5437;a[718]=5441;a[719]=5443;a[720]=5449;
a[721]=5471;a[722]=5477;a[723]=5479;a[724]=5483;a[725]=5501;a[726]=5503;a[727]=5507;a[728]=5519;a[729]=5521;a[730]=5527;
a[731]=5531;a[732]=5557;a[733]=5563;a[734]=5569;a[735]=5573;a[736]=5581;a[737]=5591;a[738]=5623;a[739]=5639;a[740]=5641;
a[741]=5647;a[742]=5651;a[743]=5653;a[744]=5657;a[745]=5659;a[746]=5669;a[747]=5683;a[748]=5689;a[749]=5693;a[750]=5701;
a[751]=5711;a[752]=5717;a[753]=5737;a[754]=5741;a[755]=5743;a[756]=5749;a[757]=5779;a[758]=5783;a[759]=5791;a[760]=5801;
a[761]=5807;a[762]=5813;a[763]=5821;a[764]=5827;a[765]=5839;a[766]=5843;a[767]=5849;a[768]=5851;a[769]=5857;a[770]=5861;
a[771]=5867;a[772]=5869;a[773]=5879;a[774]=5881;a[775]=5897;a[776]=5903;a[777]=5923;a[778]=5927;a[779]=5939;a[780]=5953;
a[781]=5981;a[782]=5987;a[783]=6007;a[784]=6011;a[785]=6029;a[786]=6037;a[787]=6043;a[788]=6047;a[789]=6053;a[790]=6067;
a[791]=6073;a[792]=6079;a[793]=6089;a[794]=6091;a[795]=6101;a[796]=6113;a[797]=6121;a[798]=6131;a[799]=6133;a[800]=6143;
a[801]=6151;a[802]=6163;a[803]=6173;a[804]=6197;a[805]=6199;a[806]=6203;a[807]=6211;a[808]=6217;a[809]=6221;a[810]=6229;
a[811]=6247;a[812]=6257;a[813]=6263;a[814]=6269;a[815]=6271;a[816]=6277;a[817]=6287;a[818]=6299;a[819]=6301;a[820]=6311;
a[821]=6317;a[822]=6323;a[823]=6329;a[824]=6337;a[825]=6343;a[826]=6353;a[827]=6359;a[828]=6361;a[829]=6367;a[830]=6373;
a[831]=6379;a[832]=6389;a[833]=6397;a[834]=6421;a[835]=6427;a[836]=6449;a[837]=6451;a[838]=6469;a[839]=6473;a[840]=6481;
a[841]=6491;a[842]=6521;a[843]=6529;a[844]=6547;a[845]=6551;a[846]=6553;a[847]=6563;a[848]=6569;a[849]=6571;a[850]=6577;
a[851]=6581;a[852]=6599;a[853]=6607;a[854]=6619;a[855]=6637;a[856]=6653;a[857]=6659;a[858]=6661;a[859]=6673;a[860]=6679;
a[861]=6689;a[862]=6691;a[863]=6701;a[864]=6703;a[865]=6709;a[866]=6719;a[867]=6733;a[868]=6737;a[869]=6761;a[870]=6763;
a[871]=6779;a[872]=6781;a[873]=6791;a[874]=6793;a[875]=6803;a[876]=6823;a[877]=6827;a[878]=6829;a[879]=6833;a[880]=6841;
a[881]=6857;a[882]=6863;a[883]=6869;a[884]=6871;a[885]=6883;a[886]=6899;a[887]=6907;a[888]=6911;a[889]=6917;a[890]=6947;
a[891]=6949;a[892]=6959;a[893]=6961;a[894]=6967;a[895]=6971;a[896]=6977;a[897]=6983;a[898]=6991;a[899]=6997;a[900]=7001;
a[901]=7013;a[902]=7019;a[903]=7027;a[904]=7039;a[905]=7043;a[906]=7057;a[907]=7069;a[908]=7079;a[909]=7103;a[910]=7109;
a[911]=7121;a[912]=7127;a[913]=7129;a[914]=7151;a[915]=7159;a[916]=7177;a[917]=7187;a[918]=7193;a[919]=7207;a[920]=7211;
a[921]=7213;a[922]=7219;a[923]=7229;a[924]=7237;a[925]=7243;a[926]=7247;a[927]=7253;a[928]=7283;a[929]=7297;a[930]=7307;
a[931]=7309;a[932]=7321;a[933]=7331;a[934]=7333;a[935]=7349;a[936]=7351;a[937]=7369;a[938]=7393;a[939]=7411;a[940]=7417;
a[941]=7433;a[942]=7451;a[943]=7457;a[944]=7459;a[945]=7477;a[946]=7481;a[947]=7487;a[948]=7489;a[949]=7499;a[950]=7507;
a[951]=7517;a[952]=7523;a[953]=7529;a[954]=7537;a[955]=7541;a[956]=7547;a[957]=7549;a[958]=7559;a[959]=7561;a[960]=7573;
a[961]=7577;a[962]=7583;a[963]=7589;a[964]=7591;a[965]=7603;a[966]=7607;a[967]=7621;a[968]=7639;a[969]=7643;a[970]=7649;
a[971]=7669;a[972]=7673;a[973]=7681;a[974]=7687;a[975]=7691;a[976]=7699;a[977]=7703;a[978]=7717;a[979]=7723;a[980]=7727;
a[981]=7741;a[982]=7753;a[983]=7757;a[984]=7759;a[985]=7789;a[986]=7793;a[987]=7817;a[988]=7823;a[989]=7829;a[990]=7841;
a[991]=7853;a[992]=7867;a[993]=7873;a[994]=7877;a[995]=7879;a[996]=7883;a[997]=7901;a[998]=7907;a[999]=7919;a[1000]=7927;
a[1001]=7933;a[1002]=7937;a[1003]=7949;a[1004]=7951;a[1005]=7963;a[1006]=7993;a[1007]=8009;a[1008]=8011;a[1009]=8017;a[1010]=8039;
a[1011]=8053;a[1012]=8059;a[1013]=8069;a[1014]=8081;a[1015]=8087;a[1016]=8089;a[1017]=8093;a[1018]=8101;a[1019]=8111;a[1020]=8117;
a[1021]=8123;a[1022]=8147;a[1023]=8161;a[1024]=8167;a[1025]=8171;a[1026]=8179;a[1027]=8191;a[1028]=8209;a[1029]=8219;a[1030]=8221;
a[1031]=8231;a[1032]=8233;a[1033]=8237;a[1034]=8243;a[1035]=8263;a[1036]=8269;a[1037]=8273;a[1038]=8287;a[1039]=8291;a[1040]=8293;
a[1041]=8297;a[1042]=8311;a[1043]=8317;a[1044]=8329;a[1045]=8353;a[1046]=8363;a[1047]=8369;a[1048]=8377;a[1049]=8387;a[1050]=8389;
a[1051]=8419;a[1052]=8423;a[1053]=8429;a[1054]=8431;a[1055]=8443;a[1056]=8447;a[1057]=8461;a[1058]=8467;a[1059]=8501;a[1060]=8513;
a[1061]=8521;a[1062]=8527;a[1063]=8537;a[1064]=8539;a[1065]=8543;a[1066]=8563;a[1067]=8573;a[1068]=8581;a[1069]=8597;a[1070]=8599;
a[1071]=8609;a[1072]=8623;a[1073]=8627;a[1074]=8629;a[1075]=8641;a[1076]=8647;a[1077]=8663;a[1078]=8669;a[1079]=8677;a[1080]=8681;
a[1081]=8689;a[1082]=8693;a[1083]=8699;a[1084]=8707;a[1085]=8713;a[1086]=8719;a[1087]=8731;a[1088]=8737;a[1089]=8741;a[1090]=8747;
a[1091]=8753;a[1092]=8761;a[1093]=8779;a[1094]=8783;a[1095]=8803;a[1096]=8807;a[1097]=8819;a[1098]=8821;a[1099]=8831;a[1100]=8837;
a[1101]=8839;a[1102]=8849;a[1103]=8861;a[1104]=8863;a[1105]=8867;a[1106]=8887;a[1107]=8893;a[1108]=8923;a[1109]=8929;a[1110]=8933;
a[1111]=8941;a[1112]=8951;a[1113]=8963;a[1114]=8969;a[1115]=8971;a[1116]=8999;a[1117]=9001;a[1118]=9007;a[1119]=9011;a[1120]=9013;
a[1121]=9029;a[1122]=9041;a[1123]=9043;a[1124]=9049;a[1125]=9059;a[1126]=9067;a[1127]=9091;a[1128]=9103;a[1129]=9109;a[1130]=9127;
a[1131]=9133;a[1132]=9137;a[1133]=9151;a[1134]=9157;a[1135]=9161;a[1136]=9173;a[1137]=9181;a[1138]=9187;a[1139]=9199;a[1140]=9203;
a[1141]=9209;a[1142]=9221;a[1143]=9227;a[1144]=9239;a[1145]=9241;a[1146]=9257;a[1147]=9277;a[1148]=9281;a[1149]=9283;a[1150]=9293;
a[1151]=9311;a[1152]=9319;a[1153]=9323;a[1154]=9337;a[1155]=9341;a[1156]=9343;a[1157]=9349;a[1158]=9371;a[1159]=9377;a[1160]=9391;
a[1161]=9397;a[1162]=9403;a[1163]=9413;a[1164]=9419;a[1165]=9421;a[1166]=9431;a[1167]=9433;a[1168]=9437;a[1169]=9439;a[1170]=9461;
a[1171]=9463;a[1172]=9467;a[1173]=9473;a[1174]=9479;a[1175]=9491;a[1176]=9497;a[1177]=9511;a[1178]=9521;a[1179]=9533;a[1180]=9539;
a[1181]=9547;a[1182]=9551;a[1183]=9587;a[1184]=9601;a[1185]=9613;a[1186]=9619;a[1187]=9623;a[1188]=9629;a[1189]=9631;a[1190]=9643;
a[1191]=9649;a[1192]=9661;a[1193]=9677;a[1194]=9679;a[1195]=9689;a[1196]=9697;a[1197]=9719;a[1198]=9721;a[1199]=9733;a[1200]=9739;
a[1201]=9743;a[1202]=9749;a[1203]=9767;a[1204]=9769;a[1205]=9781;a[1206]=9787;a[1207]=9791;a[1208]=9803;a[1209]=9811;a[1210]=9817;
a[1211]=9829;a[1212]=9833;a[1213]=9839;a[1214]=9851;a[1215]=9857;a[1216]=9859;a[1217]=9871;a[1218]=9883;a[1219]=9887;a[1220]=9901;
a[1221]=9907;a[1222]=9923;a[1223]=9929;a[1224]=9931;a[1225]=9941;a[1226]=9949;a[1227]=9967;a[1228]=9973;a[1229]=10007;a[1230]=10009;
a[1231]=10037;a[1232]=10039;a[1233]=10061;a[1234]=10067;a[1235]=10069;a[1236]=10079;a[1237]=10091;a[1238]=10093;a[1239]=10099;a[1240]=10103;
a[1241]=10111;a[1242]=10133;a[1243]=10139;a[1244]=10141;a[1245]=10151;a[1246]=10159;a[1247]=10163;a[1248]=10169;a[1249]=10177;a[1250]=10181;
a[1251]=10193;a[1252]=10211;a[1253]=10223;a[1254]=10243;a[1255]=10247;a[1256]=10253;a[1257]=10259;a[1258]=10267;a[1259]=10271;a[1260]=10273;
a[1261]=10289;a[1262]=10301;a[1263]=10303;a[1264]=10313;a[1265]=10321;a[1266]=10331;a[1267]=10333;a[1268]=10337;a[1269]=10343;a[1270]=10357;
a[1271]=10369;a[1272]=10391;a[1273]=10399;a[1274]=10427;a[1275]=10429;a[1276]=10433;a[1277]=10453;a[1278]=10457;a[1279]=10459;a[1280]=10463;
a[1281]=10477;a[1282]=10487;a[1283]=10499;a[1284]=10501;a[1285]=10513;a[1286]=10529;a[1287]=10531;a[1288]=10559;a[1289]=10567;a[1290]=10589;
a[1291]=10597;a[1292]=10601;a[1293]=10607;a[1294]=10613;a[1295]=10627;a[1296]=10631;a[1297]=10639;a[1298]=10651;a[1299]=10657;a[1300]=10663;
a[1301]=10667;a[1302]=10687;a[1303]=10691;a[1304]=10709;a[1305]=10711;a[1306]=10723;a[1307]=10729;a[1308]=10733;a[1309]=10739;a[1310]=10753;
a[1311]=10771;a[1312]=10781;a[1313]=10789;a[1314]=10799;a[1315]=10831;a[1316]=10837;a[1317]=10847;a[1318]=10853;a[1319]=10859;a[1320]=10861;
a[1321]=10867;a[1322]=10883;a[1323]=10889;a[1324]=10891;a[1325]=10903;a[1326]=10909;a[1327]=10937;a[1328]=10939;a[1329]=10949;a[1330]=10957;
a[1331]=10973;a[1332]=10979;a[1333]=10987;a[1334]=10993;a[1335]=11003;a[1336]=11027;a[1337]=11047;a[1338]=11057;a[1339]=11059;a[1340]=11069;
a[1341]=11071;a[1342]=11083;a[1343]=11087;a[1344]=11093;a[1345]=11113;a[1346]=11117;a[1347]=11119;a[1348]=11131;a[1349]=11149;a[1350]=11159;
a[1351]=11161;a[1352]=11171;a[1353]=11173;a[1354]=11177;a[1355]=11197;a[1356]=11213;a[1357]=11239;a[1358]=11243;a[1359]=11251;a[1360]=11257;
a[1361]=11261;a[1362]=11273;a[1363]=11279;a[1364]=11287;a[1365]=11299;a[1366]=11311;a[1367]=11317;a[1368]=11321;a[1369]=11329;a[1370]=11351;
a[1371]=11353;a[1372]=11369;a[1373]=11383;a[1374]=11393;a[1375]=11399;a[1376]=11411;a[1377]=11423;a[1378]=11437;a[1379]=11443;a[1380]=11447;
a[1381]=11467;a[1382]=11471;a[1383]=11483;a[1384]=11489;a[1385]=11491;a[1386]=11497;a[1387]=11503;a[1388]=11519;a[1389]=11527;a[1390]=11549;
a[1391]=11551;a[1392]=11579;a[1393]=11587;a[1394]=11593;a[1395]=11597;a[1396]=11617;a[1397]=11621;a[1398]=11633;a[1399]=11657;a[1400]=11677;
a[1401]=11681;a[1402]=11689;a[1403]=11699;a[1404]=11701;a[1405]=11717;a[1406]=11719;a[1407]=11731;a[1408]=11743;a[1409]=11777;a[1410]=11779;
a[1411]=11783;a[1412]=11789;a[1413]=11801;a[1414]=11807;a[1415]=11813;a[1416]=11821;a[1417]=11827;a[1418]=11831;a[1419]=11833;a[1420]=11839;
a[1421]=11863;a[1422]=11867;a[1423]=11887;a[1424]=11897;a[1425]=11903;a[1426]=11909;a[1427]=11923;a[1428]=11927;a[1429]=11933;a[1430]=11939;
a[1431]=11941;a[1432]=11953;a[1433]=11959;a[1434]=11969;a[1435]=11971;a[1436]=11981;a[1437]=11987;a[1438]=12007;a[1439]=12011;a[1440]=12037;
a[1441]=12041;a[1442]=12043;a[1443]=12049;a[1444]=12071;a[1445]=12073;a[1446]=12097;a[1447]=12101;a[1448]=12107;a[1449]=12109;a[1450]=12113;
a[1451]=12119;a[1452]=12143;a[1453]=12149;a[1454]=12157;a[1455]=12161;a[1456]=12163;a[1457]=12197;a[1458]=12203;a[1459]=12211;a[1460]=12227;
a[1461]=12239;a[1462]=12241;a[1463]=12251;a[1464]=12253;a[1465]=12263;a[1466]=12269;a[1467]=12277;a[1468]=12281;a[1469]=12289;a[1470]=12301;
a[1471]=12323;a[1472]=12329;a[1473]=12343;a[1474]=12347;a[1475]=12373;a[1476]=12377;a[1477]=12379;a[1478]=12391;a[1479]=12401;a[1480]=12409;
a[1481]=12413;a[1482]=12421;a[1483]=12433;a[1484]=12437;a[1485]=12451;a[1486]=12457;a[1487]=12473;a[1488]=12479;a[1489]=12487;a[1490]=12491;
a[1491]=12497;a[1492]=12503;a[1493]=12511;a[1494]=12517;a[1495]=12527;a[1496]=12539;a[1497]=12541;a[1498]=12547;a[1499]=12553;a[1500]=12569;
a[1501]=12577;a[1502]=12583;a[1503]=12589;a[1504]=12601;a[1505]=12611;a[1506]=12613;a[1507]=12619;a[1508]=12637;a[1509]=12641;a[1510]=12647;
a[1511]=12653;a[1512]=12659;a[1513]=12671;a[1514]=12689;a[1515]=12697;a[1516]=12703;a[1517]=12713;a[1518]=12721;a[1519]=12739;a[1520]=12743;
a[1521]=12757;a[1522]=12763;a[1523]=12781;a[1524]=12791;a[1525]=12799;a[1526]=12809;a[1527]=12821;a[1528]=12823;a[1529]=12829;a[1530]=12841;
a[1531]=12853;a[1532]=12889;a[1533]=12893;a[1534]=12899;a[1535]=12907;a[1536]=12911;a[1537]=12917;a[1538]=12919;a[1539]=12923;a[1540]=12941;
a[1541]=12953;a[1542]=12959;a[1543]=12967;a[1544]=12973;a[1545]=12979;a[1546]=12983;a[1547]=13001;a[1548]=13003;a[1549]=13007;a[1550]=13009;
a[1551]=13033;a[1552]=13037;a[1553]=13043;a[1554]=13049;a[1555]=13063;a[1556]=13093;a[1557]=13099;a[1558]=13103;a[1559]=13109;a[1560]=13121;
a[1561]=13127;a[1562]=13147;a[1563]=13151;a[1564]=13159;a[1565]=13163;a[1566]=13171;a[1567]=13177;a[1568]=13183;a[1569]=13187;a[1570]=13217;
a[1571]=13219;a[1572]=13229;a[1573]=13241;a[1574]=13249;a[1575]=13259;a[1576]=13267;a[1577]=13291;a[1578]=13297;a[1579]=13309;a[1580]=13313;
a[1581]=13327;a[1582]=13331;a[1583]=13337;a[1584]=13339;a[1585]=13367;a[1586]=13381;a[1587]=13397;a[1588]=13399;a[1589]=13411;a[1590]=13417;
a[1591]=13421;a[1592]=13441;a[1593]=13451;a[1594]=13457;a[1595]=13463;a[1596]=13469;a[1597]=13477;a[1598]=13487;a[1599]=13499;a[1600]=13513;
a[1601]=13523;a[1602]=13537;a[1603]=13553;a[1604]=13567;a[1605]=13577;a[1606]=13591;a[1607]=13597;a[1608]=13613;a[1609]=13619;a[1610]=13627;
a[1611]=13633;a[1612]=13649;a[1613]=13669;a[1614]=13679;a[1615]=13681;a[1616]=13687;a[1617]=13691;a[1618]=13693;a[1619]=13697;a[1620]=13709;
a[1621]=13711;a[1622]=13721;a[1623]=13723;a[1624]=13729;a[1625]=13751;a[1626]=13757;a[1627]=13759;a[1628]=13763;a[1629]=13781;a[1630]=13789;
a[1631]=13799;a[1632]=13807;a[1633]=13829;a[1634]=13831;a[1635]=13841;a[1636]=13859;a[1637]=13873;a[1638]=13877;a[1639]=13879;a[1640]=13883;
a[1641]=13901;a[1642]=13903;a[1643]=13907;a[1644]=13913;a[1645]=13921;a[1646]=13931;a[1647]=13933;a[1648]=13963;a[1649]=13967;a[1650]=13997;
a[1651]=13999;a[1652]=14009;a[1653]=14011;a[1654]=14029;a[1655]=14033;a[1656]=14051;a[1657]=14057;a[1658]=14071;a[1659]=14081;a[1660]=14083;
a[1661]=14087;a[1662]=14107;a[1663]=14143;a[1664]=14149;a[1665]=14153;a[1666]=14159;a[1667]=14173;a[1668]=14177;a[1669]=14197;a[1670]=14207;
a[1671]=14221;a[1672]=14243;a[1673]=14249;a[1674]=14251;a[1675]=14281;a[1676]=14293;a[1677]=14303;a[1678]=14321;a[1679]=14323;a[1680]=14327;
a[1681]=14341;a[1682]=14347;a[1683]=14369;a[1684]=14387;a[1685]=14389;a[1686]=14401;a[1687]=14407;a[1688]=14411;a[1689]=14419;a[1690]=14423;
a[1691]=14431;a[1692]=14437;a[1693]=14447;a[1694]=14449;a[1695]=14461;a[1696]=14479;a[1697]=14489;a[1698]=14503;a[1699]=14519;a[1700]=14533;
a[1701]=14537;a[1702]=14543;a[1703]=14549;a[1704]=14551;a[1705]=14557;a[1706]=14561;a[1707]=14563;a[1708]=14591;a[1709]=14593;a[1710]=14621;
a[1711]=14627;a[1712]=14629;a[1713]=14633;a[1714]=14639;a[1715]=14653;a[1716]=14657;a[1717]=14669;a[1718]=14683;a[1719]=14699;a[1720]=14713;
a[1721]=14717;a[1722]=14723;a[1723]=14731;a[1724]=14737;a[1725]=14741;a[1726]=14747;a[1727]=14753;a[1728]=14759;a[1729]=14767;a[1730]=14771;
a[1731]=14779;a[1732]=14783;a[1733]=14797;a[1734]=14813;a[1735]=14821;a[1736]=14827;a[1737]=14831;a[1738]=14843;a[1739]=14851;a[1740]=14867;
a[1741]=14869;a[1742]=14879;a[1743]=14887;a[1744]=14891;a[1745]=14897;a[1746]=14923;a[1747]=14929;a[1748]=14939;a[1749]=14947;a[1750]=14951;
a[1751]=14957;a[1752]=14969;a[1753]=14983;a[1754]=15013;a[1755]=15017;a[1756]=15031;a[1757]=15053;a[1758]=15061;a[1759]=15073;a[1760]=15077;
a[1761]=15083;a[1762]=15091;a[1763]=15101;a[1764]=15107;a[1765]=15121;a[1766]=15131;a[1767]=15137;a[1768]=15139;a[1769]=15149;a[1770]=15161;
a[1771]=15173;a[1772]=15187;a[1773]=15193;a[1774]=15199;a[1775]=15217;a[1776]=15227;a[1777]=15233;a[1778]=15241;a[1779]=15259;a[1780]=15263;
a[1781]=15269;a[1782]=15271;a[1783]=15277;a[1784]=15287;a[1785]=15289;a[1786]=15299;a[1787]=15307;a[1788]=15313;a[1789]=15319;a[1790]=15329;
a[1791]=15331;a[1792]=15349;a[1793]=15359;a[1794]=15361;a[1795]=15373;a[1796]=15377;a[1797]=15383;a[1798]=15391;a[1799]=15401;a[1800]=15413;
a[1801]=15427;a[1802]=15439;a[1803]=15443;a[1804]=15451;a[1805]=15461;a[1806]=15467;a[1807]=15473;a[1808]=15493;a[1809]=15497;a[1810]=15511;
a[1811]=15527;a[1812]=15541;a[1813]=15551;a[1814]=15559;a[1815]=15569;a[1816]=15581;a[1817]=15583;a[1818]=15601;a[1819]=15607;a[1820]=15619;
a[1821]=15629;a[1822]=15641;a[1823]=15643;a[1824]=15647;a[1825]=15649;a[1826]=15661;a[1827]=15667;a[1828]=15671;a[1829]=15679;a[1830]=15683;
a[1831]=15727;a[1832]=15731;a[1833]=15733;a[1834]=15737;a[1835]=15739;a[1836]=15749;a[1837]=15761;a[1838]=15767;a[1839]=15773;a[1840]=15787;
a[1841]=15791;a[1842]=15797;a[1843]=15803;a[1844]=15809;a[1845]=15817;a[1846]=15823;a[1847]=15859;a[1848]=15877;a[1849]=15881;a[1850]=15887;
a[1851]=15889;a[1852]=15901;a[1853]=15907;a[1854]=15913;a[1855]=15919;a[1856]=15923;a[1857]=15937;a[1858]=15959;a[1859]=15971;a[1860]=15973;
a[1861]=15991;a[1862]=16001;a[1863]=16007;a[1864]=16033;a[1865]=16057;a[1866]=16061;a[1867]=16063;a[1868]=16067;a[1869]=16069;a[1870]=16073;
a[1871]=16087;a[1872]=16091;a[1873]=16097;a[1874]=16103;a[1875]=16111;a[1876]=16127;a[1877]=16139;a[1878]=16141;a[1879]=16183;a[1880]=16187;
a[1881]=16189;a[1882]=16193;a[1883]=16217;a[1884]=16223;a[1885]=16229;a[1886]=16231;a[1887]=16249;a[1888]=16253;a[1889]=16267;a[1890]=16273;
a[1891]=16301;a[1892]=16319;a[1893]=16333;a[1894]=16339;a[1895]=16349;a[1896]=16361;a[1897]=16363;a[1898]=16369;a[1899]=16381;a[1900]=16411;
a[1901]=16417;a[1902]=16421;a[1903]=16427;a[1904]=16433;a[1905]=16447;a[1906]=16451;a[1907]=16453;a[1908]=16477;a[1909]=16481;a[1910]=16487;
a[1911]=16493;a[1912]=16519;a[1913]=16529;a[1914]=16547;a[1915]=16553;a[1916]=16561;a[1917]=16567;a[1918]=16573;a[1919]=16603;a[1920]=16607;
a[1921]=16619;a[1922]=16631;a[1923]=16633;a[1924]=16649;a[1925]=16651;a[1926]=16657;a[1927]=16661;a[1928]=16673;a[1929]=16691;a[1930]=16693;
a[1931]=16699;a[1932]=16703;a[1933]=16729;a[1934]=16741;a[1935]=16747;a[1936]=16759;a[1937]=16763;a[1938]=16787;a[1939]=16811;a[1940]=16823;
a[1941]=16829;a[1942]=16831;a[1943]=16843;a[1944]=16871;a[1945]=16879;a[1946]=16883;a[1947]=16889;a[1948]=16901;a[1949]=16903;a[1950]=16921;
a[1951]=16927;a[1952]=16931;a[1953]=16937;a[1954]=16943;a[1955]=16963;a[1956]=16979;a[1957]=16981;a[1958]=16987;a[1959]=16993;a[1960]=17011;
a[1961]=17021;a[1962]=17027;a[1963]=17029;a[1964]=17033;a[1965]=17041;a[1966]=17047;a[1967]=17053;a[1968]=17077;a[1969]=17093;a[1970]=17099;
a[1971]=17107;a[1972]=17117;a[1973]=17123;a[1974]=17137;a[1975]=17159;a[1976]=17167;a[1977]=17183;a[1978]=17189;a[1979]=17191;a[1980]=17203;
a[1981]=17207;a[1982]=17209;a[1983]=17231;a[1984]=17239;a[1985]=17257;a[1986]=17291;a[1987]=17293;a[1988]=17299;a[1989]=17317;a[1990]=17321;
a[1991]=17327;a[1992]=17333;a[1993]=17341;a[1994]=17351;a[1995]=17359;a[1996]=17377;a[1997]=17383;a[1998]=17387;a[1999]=17389;a[2000]=17393;
a[2001]=17401;a[2002]=17417;a[2003]=17419;a[2004]=17431;a[2005]=17443;a[2006]=17449;a[2007]=17467;a[2008]=17471;a[2009]=17477;a[2010]=17483;
a[2011]=17489;a[2012]=17491;a[2013]=17497;a[2014]=17509;a[2015]=17519;a[2016]=17539;a[2017]=17551;a[2018]=17569;a[2019]=17573;a[2020]=17579;
a[2021]=17581;a[2022]=17597;a[2023]=17599;a[2024]=17609;a[2025]=17623;a[2026]=17627;a[2027]=17657;a[2028]=17659;a[2029]=17669;a[2030]=17681;
a[2031]=17683;a[2032]=17707;a[2033]=17713;a[2034]=17729;a[2035]=17737;a[2036]=17747;a[2037]=17749;a[2038]=17761;a[2039]=17783;a[2040]=17789;
a[2041]=17791;a[2042]=17807;a[2043]=17827;a[2044]=17837;a[2045]=17839;a[2046]=17851;a[2047]=17863;a[2048]=17881;a[2049]=17891;a[2050]=17903;
a[2051]=17909;a[2052]=17911;a[2053]=17921;a[2054]=17923;a[2055]=17929;a[2056]=17939;a[2057]=17957;a[2058]=17959;a[2059]=17971;a[2060]=17977;
a[2061]=17981;a[2062]=17987;a[2063]=17989;a[2064]=18013;a[2065]=18041;a[2066]=18043;a[2067]=18047;a[2068]=18049;a[2069]=18059;a[2070]=18061;
a[2071]=18077;a[2072]=18089;a[2073]=18097;a[2074]=18119;a[2075]=18121;a[2076]=18127;a[2077]=18131;a[2078]=18133;a[2079]=18143;a[2080]=18149;
a[2081]=18169;a[2082]=18181;a[2083]=18191;a[2084]=18199;a[2085]=18211;a[2086]=18217;a[2087]=18223;a[2088]=18229;a[2089]=18233;a[2090]=18251;
a[2091]=18253;a[2092]=18257;a[2093]=18269;a[2094]=18287;a[2095]=18289;a[2096]=18301;a[2097]=18307;a[2098]=18311;a[2099]=18313;a[2100]=18329;
a[2101]=18341;a[2102]=18353;a[2103]=18367;a[2104]=18371;a[2105]=18379;a[2106]=18397;a[2107]=18401;a[2108]=18413;a[2109]=18427;a[2110]=18433;
a[2111]=18439;a[2112]=18443;a[2113]=18451;a[2114]=18457;a[2115]=18461;a[2116]=18481;a[2117]=18493;a[2118]=18503;a[2119]=18517;a[2120]=18521;
a[2121]=18523;a[2122]=18539;a[2123]=18541;a[2124]=18553;a[2125]=18583;a[2126]=18587;a[2127]=18593;a[2128]=18617;a[2129]=18637;a[2130]=18661;
a[2131]=18671;a[2132]=18679;a[2133]=18691;a[2134]=18701;a[2135]=18713;a[2136]=18719;a[2137]=18731;a[2138]=18743;a[2139]=18749;a[2140]=18757;
a[2141]=18773;a[2142]=18787;a[2143]=18793;a[2144]=18797;a[2145]=18803;a[2146]=18839;a[2147]=18859;a[2148]=18869;a[2149]=18899;a[2150]=18911;
a[2151]=18913;a[2152]=18917;a[2153]=18919;a[2154]=18947;a[2155]=18959;a[2156]=18973;a[2157]=18979;a[2158]=19001;a[2159]=19009;a[2160]=19013;
a[2161]=19031;a[2162]=19037;a[2163]=19051;a[2164]=19069;a[2165]=19073;a[2166]=19079;a[2167]=19081;a[2168]=19087;a[2169]=19121;a[2170]=19139;
a[2171]=19141;a[2172]=19157;a[2173]=19163;a[2174]=19181;a[2175]=19183;a[2176]=19207;a[2177]=19211;a[2178]=19213;a[2179]=19219;a[2180]=19231;
a[2181]=19237;a[2182]=19249;a[2183]=19259;a[2184]=19267;a[2185]=19273;a[2186]=19289;a[2187]=19301;a[2188]=19309;a[2189]=19319;a[2190]=19333;
a[2191]=19373;a[2192]=19379;a[2193]=19381;a[2194]=19387;a[2195]=19391;a[2196]=19403;a[2197]=19417;a[2198]=19421;a[2199]=19423;a[2200]=19427;
a[2201]=19429;a[2202]=19433;a[2203]=19441;a[2204]=19447;a[2205]=19457;a[2206]=19463;a[2207]=19469;a[2208]=19471;a[2209]=19477;a[2210]=19483;
a[2211]=19489;a[2212]=19501;a[2213]=19507;a[2214]=19531;a[2215]=19541;a[2216]=19543;a[2217]=19553;a[2218]=19559;a[2219]=19571;a[2220]=19577;
a[2221]=19583;a[2222]=19597;a[2223]=19603;a[2224]=19609;a[2225]=19661;a[2226]=19681;a[2227]=19687;a[2228]=19697;a[2229]=19699;a[2230]=19709;
a[2231]=19717;a[2232]=19727;a[2233]=19739;a[2234]=19751;a[2235]=19753;a[2236]=19759;a[2237]=19763;a[2238]=19777;a[2239]=19793;a[2240]=19801;
a[2241]=19813;a[2242]=19819;a[2243]=19841;a[2244]=19843;a[2245]=19853;a[2246]=19861;a[2247]=19867;a[2248]=19889;a[2249]=19891;a[2250]=19913;
a[2251]=19919;a[2252]=19927;a[2253]=19937;a[2254]=19949;a[2255]=19961;a[2256]=19963;a[2257]=19973;a[2258]=19979;a[2259]=19991;a[2260]=19993;
a[2261]=19997;a[2262]=20011;a[2263]=20021;a[2264]=20023;a[2265]=20029;a[2266]=20047;a[2267]=20051;a[2268]=20063;a[2269]=20071;a[2270]=20089;
a[2271]=20101;a[2272]=20107;a[2273]=20113;a[2274]=20117;a[2275]=20123;a[2276]=20129;a[2277]=20143;a[2278]=20147;a[2279]=20149;a[2280]=20161;
a[2281]=20173;a[2282]=20177;a[2283]=20183;a[2284]=20201;a[2285]=20219;a[2286]=20231;a[2287]=20233;a[2288]=20249;a[2289]=20261;a[2290]=20269;
a[2291]=20287;a[2292]=20297;a[2293]=20323;a[2294]=20327;a[2295]=20333;a[2296]=20341;a[2297]=20347;a[2298]=20353;a[2299]=20357;a[2300]=20359;
a[2301]=20369;a[2302]=20389;a[2303]=20393;a[2304]=20399;a[2305]=20407;a[2306]=20411;a[2307]=20431;a[2308]=20441;a[2309]=20443;a[2310]=20477;
a[2311]=20479;a[2312]=20483;a[2313]=20507;a[2314]=20509;a[2315]=20521;a[2316]=20533;a[2317]=20543;a[2318]=20549;a[2319]=20551;a[2320]=20563;
a[2321]=20593;a[2322]=20599;a[2323]=20611;a[2324]=20627;a[2325]=20639;a[2326]=20641;a[2327]=20663;a[2328]=20681;a[2329]=20693;a[2330]=20707;
a[2331]=20717;a[2332]=20719;a[2333]=20731;a[2334]=20743;a[2335]=20747;a[2336]=20749;a[2337]=20753;a[2338]=20759;a[2339]=20771;a[2340]=20773;
a[2341]=20789;a[2342]=20807;a[2343]=20809;a[2344]=20849;a[2345]=20857;a[2346]=20873;a[2347]=20879;a[2348]=20887;a[2349]=20897;a[2350]=20899;
a[2351]=20903;a[2352]=20921;a[2353]=20929;a[2354]=20939;a[2355]=20947;a[2356]=20959;a[2357]=20963;a[2358]=20981;a[2359]=20983;a[2360]=21001;
a[2361]=21011;a[2362]=21013;a[2363]=21017;a[2364]=21019;a[2365]=21023;a[2366]=21031;a[2367]=21059;a[2368]=21061;a[2369]=21067;a[2370]=21089;
a[2371]=21101;a[2372]=21107;a[2373]=21121;a[2374]=21139;a[2375]=21143;a[2376]=21149;a[2377]=21157;a[2378]=21163;a[2379]=21169;a[2380]=21179;
a[2381]=21187;a[2382]=21191;a[2383]=21193;a[2384]=21211;a[2385]=21221;a[2386]=21227;a[2387]=21247;a[2388]=21269;a[2389]=21277;a[2390]=21283;
a[2391]=21313;a[2392]=21317;a[2393]=21319;a[2394]=21323;a[2395]=21341;a[2396]=21347;a[2397]=21377;a[2398]=21379;a[2399]=21383;a[2400]=21391;
a[2401]=21397;a[2402]=21401;a[2403]=21407;a[2404]=21419;a[2405]=21433;a[2406]=21467;a[2407]=21481;a[2408]=21487;a[2409]=21491;a[2410]=21493;
a[2411]=21499;a[2412]=21503;a[2413]=21517;a[2414]=21521;a[2415]=21523;a[2416]=21529;a[2417]=21557;a[2418]=21559;a[2419]=21563;a[2420]=21569;
a[2421]=21577;a[2422]=21587;a[2423]=21589;a[2424]=21599;a[2425]=21601;a[2426]=21611;a[2427]=21613;a[2428]=21617;a[2429]=21647;a[2430]=21649;
a[2431]=21661;a[2432]=21673;a[2433]=21683;a[2434]=21701;a[2435]=21713;a[2436]=21727;a[2437]=21737;a[2438]=21739;a[2439]=21751;a[2440]=21757;
a[2441]=21767;a[2442]=21773;a[2443]=21787;a[2444]=21799;a[2445]=21803;a[2446]=21817;a[2447]=21821;a[2448]=21839;a[2449]=21841;a[2450]=21851;
a[2451]=21859;a[2452]=21863;a[2453]=21871;a[2454]=21881;a[2455]=21893;a[2456]=21911;a[2457]=21929;a[2458]=21937;a[2459]=21943;a[2460]=21961;
a[2461]=21977;a[2462]=21991;a[2463]=21997;a[2464]=22003;a[2465]=22013;a[2466]=22027;a[2467]=22031;a[2468]=22037;a[2469]=22039;a[2470]=22051;
a[2471]=22063;a[2472]=22067;a[2473]=22073;a[2474]=22079;a[2475]=22091;a[2476]=22093;a[2477]=22109;a[2478]=22111;a[2479]=22123;a[2480]=22129;
a[2481]=22133;a[2482]=22147;a[2483]=22153;a[2484]=22157;a[2485]=22159;a[2486]=22171;a[2487]=22189;a[2488]=22193;a[2489]=22229;a[2490]=22247;
a[2491]=22259;a[2492]=22271;a[2493]=22273;a[2494]=22277;a[2495]=22279;a[2496]=22283;a[2497]=22291;a[2498]=22303;a[2499]=22307;a[2500]=22343;
a[2501]=22349;a[2502]=22367;a[2503]=22369;a[2504]=22381;a[2505]=22391;a[2506]=22397;a[2507]=22409;a[2508]=22433;a[2509]=22441;a[2510]=22447;
a[2511]=22453;a[2512]=22469;a[2513]=22481;a[2514]=22483;a[2515]=22501;a[2516]=22511;a[2517]=22531;a[2518]=22541;a[2519]=22543;a[2520]=22549;
a[2521]=22567;a[2522]=22571;a[2523]=22573;a[2524]=22613;a[2525]=22619;a[2526]=22621;a[2527]=22637;a[2528]=22639;a[2529]=22643;a[2530]=22651;
a[2531]=22669;a[2532]=22679;a[2533]=22691;a[2534]=22697;a[2535]=22699;a[2536]=22709;a[2537]=22717;a[2538]=22721;a[2539]=22727;a[2540]=22739;
a[2541]=22741;a[2542]=22751;a[2543]=22769;a[2544]=22777;a[2545]=22783;a[2546]=22787;a[2547]=22807;a[2548]=22811;a[2549]=22817;a[2550]=22853;
a[2551]=22859;a[2552]=22861;a[2553]=22871;a[2554]=22877;a[2555]=22901;a[2556]=22907;a[2557]=22921;a[2558]=22937;a[2559]=22943;a[2560]=22961;
a[2561]=22963;a[2562]=22973;a[2563]=22993;a[2564]=23003;a[2565]=23011;a[2566]=23017;a[2567]=23021;a[2568]=23027;a[2569]=23029;a[2570]=23039;
a[2571]=23041;a[2572]=23053;a[2573]=23057;a[2574]=23059;a[2575]=23063;a[2576]=23071;a[2577]=23081;a[2578]=23087;a[2579]=23099;a[2580]=23117;
a[2581]=23131;a[2582]=23143;a[2583]=23159;a[2584]=23167;a[2585]=23173;a[2586]=23189;a[2587]=23197;a[2588]=23201;a[2589]=23203;a[2590]=23209;
a[2591]=23227;a[2592]=23251;a[2593]=23269;a[2594]=23279;a[2595]=23291;a[2596]=23293;a[2597]=23297;a[2598]=23311;a[2599]=23321;a[2600]=23327;
a[2601]=23333;a[2602]=23339;a[2603]=23357;a[2604]=23369;a[2605]=23371;a[2606]=23399;a[2607]=23417;a[2608]=23431;a[2609]=23447;a[2610]=23459;
a[2611]=23473;a[2612]=23497;a[2613]=23509;a[2614]=23531;a[2615]=23537;a[2616]=23539;a[2617]=23549;a[2618]=23557;a[2619]=23561;a[2620]=23563;
a[2621]=23567;a[2622]=23581;a[2623]=23593;a[2624]=23599;a[2625]=23603;a[2626]=23609;a[2627]=23623;a[2628]=23627;a[2629]=23629;a[2630]=23633;
a[2631]=23663;a[2632]=23669;a[2633]=23671;a[2634]=23677;a[2635]=23687;a[2636]=23689;a[2637]=23719;a[2638]=23741;a[2639]=23743;a[2640]=23747;
a[2641]=23753;a[2642]=23761;a[2643]=23767;a[2644]=23773;a[2645]=23789;a[2646]=23801;a[2647]=23813;a[2648]=23819;a[2649]=23827;a[2650]=23831;
a[2651]=23833;a[2652]=23857;a[2653]=23869;a[2654]=23873;a[2655]=23879;a[2656]=23887;a[2657]=23893;a[2658]=23899;a[2659]=23909;a[2660]=23911;
a[2661]=23917;a[2662]=23929;a[2663]=23957;a[2664]=23971;a[2665]=23977;a[2666]=23981;a[2667]=23993;a[2668]=24001;a[2669]=24007;a[2670]=24019;
a[2671]=24023;a[2672]=24029;a[2673]=24043;a[2674]=24049;a[2675]=24061;a[2676]=24071;a[2677]=24077;a[2678]=24083;a[2679]=24091;a[2680]=24097;
a[2681]=24103;a[2682]=24107;a[2683]=24109;a[2684]=24113;a[2685]=24121;a[2686]=24133;a[2687]=24137;a[2688]=24151;a[2689]=24169;a[2690]=24179;
a[2691]=24181;a[2692]=24197;a[2693]=24203;a[2694]=24223;a[2695]=24229;a[2696]=24239;a[2697]=24247;a[2698]=24251;a[2699]=24281;a[2700]=24317;
a[2701]=24329;a[2702]=24337;a[2703]=24359;a[2704]=24371;a[2705]=24373;a[2706]=24379;a[2707]=24391;a[2708]=24407;a[2709]=24413;a[2710]=24419;
a[2711]=24421;a[2712]=24439;a[2713]=24443;a[2714]=24469;a[2715]=24473;a[2716]=24481;a[2717]=24499;a[2718]=24509;a[2719]=24517;a[2720]=24527;
a[2721]=24533;a[2722]=24547;a[2723]=24551;a[2724]=24571;a[2725]=24593;a[2726]=24611;a[2727]=24623;a[2728]=24631;a[2729]=24659;a[2730]=24671;
a[2731]=24677;a[2732]=24683;a[2733]=24691;a[2734]=24697;a[2735]=24709;a[2736]=24733;a[2737]=24749;a[2738]=24763;a[2739]=24767;a[2740]=24781;
a[2741]=24793;a[2742]=24799;a[2743]=24809;a[2744]=24821;a[2745]=24841;a[2746]=24847;a[2747]=24851;a[2748]=24859;a[2749]=24877;a[2750]=24889;
a[2751]=24907;a[2752]=24917;a[2753]=24919;a[2754]=24923;a[2755]=24943;a[2756]=24953;a[2757]=24967;a[2758]=24971;a[2759]=24977;a[2760]=24979;
a[2761]=24989;a[2762]=25013;a[2763]=25031;a[2764]=25033;a[2765]=25037;a[2766]=25057;a[2767]=25073;a[2768]=25087;a[2769]=25097;a[2770]=25111;
a[2771]=25117;a[2772]=25121;a[2773]=25127;a[2774]=25147;a[2775]=25153;a[2776]=25163;a[2777]=25169;a[2778]=25171;a[2779]=25183;a[2780]=25189;
a[2781]=25219;a[2782]=25229;a[2783]=25237;a[2784]=25243;a[2785]=25247;a[2786]=25253;a[2787]=25261;a[2788]=25301;a[2789]=25303;a[2790]=25307;
a[2791]=25309;a[2792]=25321;a[2793]=25339;a[2794]=25343;a[2795]=25349;a[2796]=25357;a[2797]=25367;a[2798]=25373;a[2799]=25391;a[2800]=25409;
a[2801]=25411;a[2802]=25423;a[2803]=25439;a[2804]=25447;a[2805]=25453;a[2806]=25457;a[2807]=25463;a[2808]=25469;a[2809]=25471;a[2810]=25523;
a[2811]=25537;a[2812]=25541;a[2813]=25561;a[2814]=25577;a[2815]=25579;a[2816]=25583;a[2817]=25589;a[2818]=25601;a[2819]=25603;a[2820]=25609;
a[2821]=25621;a[2822]=25633;a[2823]=25639;a[2824]=25643;a[2825]=25657;a[2826]=25667;a[2827]=25673;a[2828]=25679;a[2829]=25693;a[2830]=25703;
a[2831]=25717;a[2832]=25733;a[2833]=25741;a[2834]=25747;a[2835]=25759;a[2836]=25763;a[2837]=25771;a[2838]=25793;a[2839]=25799;a[2840]=25801;
a[2841]=25819;a[2842]=25841;a[2843]=25847;a[2844]=25849;a[2845]=25867;a[2846]=25873;a[2847]=25889;a[2848]=25903;a[2849]=25913;a[2850]=25919;
a[2851]=25931;a[2852]=25933;a[2853]=25939;a[2854]=25943;a[2855]=25951;a[2856]=25969;a[2857]=25981;a[2858]=25997;a[2859]=25999;a[2860]=26003;
a[2861]=26017;a[2862]=26021;a[2863]=26029;a[2864]=26041;a[2865]=26053;a[2866]=26083;a[2867]=26099;a[2868]=26107;a[2869]=26111;a[2870]=26113;
a[2871]=26119;a[2872]=26141;a[2873]=26153;a[2874]=26161;a[2875]=26171;a[2876]=26177;a[2877]=26183;a[2878]=26189;a[2879]=26203;a[2880]=26209;
a[2881]=26227;a[2882]=26237;a[2883]=26249;a[2884]=26251;a[2885]=26261;a[2886]=26263;a[2887]=26267;a[2888]=26293;a[2889]=26297;a[2890]=26309;
a[2891]=26317;a[2892]=26321;a[2893]=26339;a[2894]=26347;a[2895]=26357;a[2896]=26371;a[2897]=26387;a[2898]=26393;a[2899]=26399;a[2900]=26407;
a[2901]=26417;a[2902]=26423;a[2903]=26431;a[2904]=26437;a[2905]=26449;a[2906]=26459;a[2907]=26479;a[2908]=26489;a[2909]=26497;a[2910]=26501;
a[2911]=26513;a[2912]=26539;a[2913]=26557;a[2914]=26561;a[2915]=26573;a[2916]=26591;a[2917]=26597;a[2918]=26627;a[2919]=26633;a[2920]=26641;
a[2921]=26647;a[2922]=26669;a[2923]=26681;a[2924]=26683;a[2925]=26687;a[2926]=26693;a[2927]=26699;a[2928]=26701;a[2929]=26711;a[2930]=26713;
a[2931]=26717;a[2932]=26723;a[2933]=26729;a[2934]=26731;a[2935]=26737;a[2936]=26759;a[2937]=26777;a[2938]=26783;a[2939]=26801;a[2940]=26813;
a[2941]=26821;a[2942]=26833;a[2943]=26839;a[2944]=26849;a[2945]=26861;a[2946]=26863;a[2947]=26879;a[2948]=26881;a[2949]=26891;a[2950]=26893;
a[2951]=26903;a[2952]=26921;a[2953]=26927;a[2954]=26947;a[2955]=26951;a[2956]=26953;a[2957]=26959;a[2958]=26981;a[2959]=26987;a[2960]=26993;
a[2961]=27011;a[2962]=27017;a[2963]=27031;a[2964]=27043;a[2965]=27059;a[2966]=27061;a[2967]=27067;a[2968]=27073;a[2969]=27077;a[2970]=27091;
a[2971]=27103;a[2972]=27107;a[2973]=27109;a[2974]=27127;a[2975]=27143;a[2976]=27179;a[2977]=27191;a[2978]=27197;a[2979]=27211;a[2980]=27239;
a[2981]=27241;a[2982]=27253;a[2983]=27259;a[2984]=27271;a[2985]=27277;a[2986]=27281;a[2987]=27283;a[2988]=27299;a[2989]=27329;a[2990]=27337;
a[2991]=27361;a[2992]=27367;a[2993]=27397;a[2994]=27407;a[2995]=27409;a[2996]=27427;a[2997]=27431;a[2998]=27437;a[2999]=27449;a[3000]=27457;
a[3001]=27479;a[3002]=27481;a[3003]=27487;a[3004]=27509;a[3005]=27527;a[3006]=27529;a[3007]=27539;a[3008]=27541;a[3009]=27551;a[3010]=27581;
a[3011]=27583;a[3012]=27611;a[3013]=27617;a[3014]=27631;a[3015]=27647;a[3016]=27653;a[3017]=27673;a[3018]=27689;a[3019]=27691;a[3020]=27697;
a[3021]=27701;a[3022]=27733;a[3023]=27737;a[3024]=27739;a[3025]=27743;a[3026]=27749;a[3027]=27751;a[3028]=27763;a[3029]=27767;a[3030]=27773;
a[3031]=27779;a[3032]=27791;a[3033]=27793;a[3034]=27799;a[3035]=27803;a[3036]=27809;a[3037]=27817;a[3038]=27823;a[3039]=27827;a[3040]=27847;
a[3041]=27851;a[3042]=27883;a[3043]=27893;a[3044]=27901;a[3045]=27917;a[3046]=27919;a[3047]=27941;a[3048]=27943;a[3049]=27947;a[3050]=27953;
a[3051]=27961;a[3052]=27967;a[3053]=27983;a[3054]=27997;a[3055]=28001;a[3056]=28019;a[3057]=28027;a[3058]=28031;a[3059]=28051;a[3060]=28057;
a[3061]=28069;a[3062]=28081;a[3063]=28087;a[3064]=28097;a[3065]=28099;a[3066]=28109;a[3067]=28111;a[3068]=28123;a[3069]=28151;a[3070]=28163;
a[3071]=28181;a[3072]=28183;a[3073]=28201;a[3074]=28211;a[3075]=28219;a[3076]=28229;a[3077]=28277;a[3078]=28279;a[3079]=28283;a[3080]=28289;
a[3081]=28297;a[3082]=28307;a[3083]=28309;a[3084]=28319;a[3085]=28349;a[3086]=28351;a[3087]=28387;a[3088]=28393;a[3089]=28403;a[3090]=28409;
a[3091]=28411;a[3092]=28429;a[3093]=28433;a[3094]=28439;a[3095]=28447;a[3096]=28463;a[3097]=28477;a[3098]=28493;a[3099]=28499;a[3100]=28513;
a[3101]=28517;a[3102]=28537;a[3103]=28541;a[3104]=28547;a[3105]=28549;a[3106]=28559;a[3107]=28571;a[3108]=28573;a[3109]=28579;a[3110]=28591;
a[3111]=28597;a[3112]=28603;a[3113]=28607;a[3114]=28619;a[3115]=28621;a[3116]=28627;a[3117]=28631;a[3118]=28643;a[3119]=28649;a[3120]=28657;
a[3121]=28661;a[3122]=28663;a[3123]=28669;a[3124]=28687;a[3125]=28697;a[3126]=28703;a[3127]=28711;a[3128]=28723;a[3129]=28729;a[3130]=28751;
a[3131]=28753;a[3132]=28759;a[3133]=28771;a[3134]=28789;a[3135]=28793;a[3136]=28807;a[3137]=28813;a[3138]=28817;a[3139]=28837;a[3140]=28843;
a[3141]=28859;a[3142]=28867;a[3143]=28871;a[3144]=28879;a[3145]=28901;a[3146]=28909;a[3147]=28921;a[3148]=28927;a[3149]=28933;a[3150]=28949;
a[3151]=28961;a[3152]=28979;a[3153]=29009;a[3154]=29017;a[3155]=29021;a[3156]=29023;a[3157]=29027;a[3158]=29033;a[3159]=29059;a[3160]=29063;
a[3161]=29077;a[3162]=29101;a[3163]=29123;a[3164]=29129;a[3165]=29131;a[3166]=29137;a[3167]=29147;a[3168]=29153;a[3169]=29167;a[3170]=29173;
a[3171]=29179;a[3172]=29191;a[3173]=29201;a[3174]=29207;a[3175]=29209;a[3176]=29221;a[3177]=29231;a[3178]=29243;a[3179]=29251;a[3180]=29269;
a[3181]=29287;a[3182]=29297;a[3183]=29303;a[3184]=29311;a[3185]=29327;a[3186]=29333;a[3187]=29339;a[3188]=29347;a[3189]=29363;a[3190]=29383;
a[3191]=29387;a[3192]=29389;a[3193]=29399;a[3194]=29401;a[3195]=29411;a[3196]=29423;a[3197]=29429;a[3198]=29437;a[3199]=29443;a[3200]=29453;
a[3201]=29473;a[3202]=29483;a[3203]=29501;a[3204]=29527;a[3205]=29531;a[3206]=29537;a[3207]=29567;a[3208]=29569;a[3209]=29573;a[3210]=29581;
a[3211]=29587;a[3212]=29599;a[3213]=29611;a[3214]=29629;a[3215]=29633;a[3216]=29641;a[3217]=29663;a[3218]=29669;a[3219]=29671;a[3220]=29683;
a[3221]=29717;a[3222]=29723;a[3223]=29741;a[3224]=29753;a[3225]=29759;a[3226]=29761;a[3227]=29789;a[3228]=29803;a[3229]=29819;a[3230]=29833;
a[3231]=29837;a[3232]=29851;a[3233]=29863;a[3234]=29867;a[3235]=29873;a[3236]=29879;a[3237]=29881;a[3238]=29917;a[3239]=29921;a[3240]=29927;
a[3241]=29947;a[3242]=29959;a[3243]=29983;a[3244]=29989;a[3245]=30011;a[3246]=30013;a[3247]=30029;a[3248]=30047;a[3249]=30059;a[3250]=30071;
a[3251]=30089;a[3252]=30091;a[3253]=30097;a[3254]=30103;a[3255]=30109;a[3256]=30113;a[3257]=30119;a[3258]=30133;a[3259]=30137;a[3260]=30139;
a[3261]=30161;a[3262]=30169;a[3263]=30181;a[3264]=30187;a[3265]=30197;a[3266]=30203;a[3267]=30211;a[3268]=30223;a[3269]=30241;a[3270]=30253;
a[3271]=30259;a[3272]=30269;a[3273]=30271;a[3274]=30293;a[3275]=30307;a[3276]=30313;a[3277]=30319;a[3278]=30323;a[3279]=30341;a[3280]=30347;
a[3281]=30367;a[3282]=30389;a[3283]=30391;a[3284]=30403;a[3285]=30427;a[3286]=30431;a[3287]=30449;a[3288]=30467;a[3289]=30469;a[3290]=30491;
a[3291]=30493;a[3292]=30497;a[3293]=30509;a[3294]=30517;a[3295]=30529;a[3296]=30539;a[3297]=30553;a[3298]=30557;a[3299]=30559;a[3300]=30577;
a[3301]=30593;a[3302]=30631;a[3303]=30637;a[3304]=30643;a[3305]=30649;a[3306]=30661;a[3307]=30671;a[3308]=30677;a[3309]=30689;a[3310]=30697;
a[3311]=30703;a[3312]=30707;a[3313]=30713;a[3314]=30727;a[3315]=30757;a[3316]=30763;a[3317]=30773;a[3318]=30781;a[3319]=30803;a[3320]=30809;
a[3321]=30817;a[3322]=30829;a[3323]=30839;a[3324]=30841;a[3325]=30851;a[3326]=30853;a[3327]=30859;a[3328]=30869;a[3329]=30871;a[3330]=30881;
a[3331]=30893;a[3332]=30911;a[3333]=30931;a[3334]=30937;a[3335]=30941;a[3336]=30949;a[3337]=30971;a[3338]=30977;a[3339]=30983;a[3340]=31013;
a[3341]=31019;a[3342]=31033;a[3343]=31039;a[3344]=31051;a[3345]=31063;a[3346]=31069;a[3347]=31079;a[3348]=31081;a[3349]=31091;a[3350]=31121;
a[3351]=31123;a[3352]=31139;a[3353]=31147;a[3354]=31151;a[3355]=31153;a[3356]=31159;a[3357]=31177;a[3358]=31181;a[3359]=31183;a[3360]=31189;
a[3361]=31193;a[3362]=31219;a[3363]=31223;a[3364]=31231;a[3365]=31237;a[3366]=31247;a[3367]=31249;a[3368]=31253;a[3369]=31259;a[3370]=31267;
a[3371]=31271;a[3372]=31277;a[3373]=31307;a[3374]=31319;a[3375]=31321;a[3376]=31327;a[3377]=31333;a[3378]=31337;a[3379]=31357;a[3380]=31379;
a[3381]=31387;a[3382]=31391;a[3383]=31393;a[3384]=31397;a[3385]=31469;a[3386]=31477;a[3387]=31481;a[3388]=31489;a[3389]=31511;a[3390]=31513;
a[3391]=31517;a[3392]=31531;a[3393]=31541;a[3394]=31543;a[3395]=31547;a[3396]=31567;a[3397]=31573;a[3398]=31583;a[3399]=31601;a[3400]=31607;
a[3401]=31627;a[3402]=31643;a[3403]=31649;a[3404]=31657;a[3405]=31663;a[3406]=31667;a[3407]=31687;a[3408]=31699;a[3409]=31721;a[3410]=31723;
a[3411]=31727;a[3412]=31729;a[3413]=31741;a[3414]=31751;a[3415]=31769;a[3416]=31771;a[3417]=31793;a[3418]=31799;a[3419]=31817;a[3420]=31847;
a[3421]=31849;a[3422]=31859;a[3423]=31873;a[3424]=31883;a[3425]=31891;a[3426]=31907;a[3427]=31957;a[3428]=31963;a[3429]=31973;a[3430]=31981;
a[3431]=31991;a[3432]=32003;a[3433]=32009;a[3434]=32027;a[3435]=32029;a[3436]=32051;a[3437]=32057;a[3438]=32059;a[3439]=32063;a[3440]=32069;
a[3441]=32077;a[3442]=32083;a[3443]=32089;a[3444]=32099;a[3445]=32117;a[3446]=32119;a[3447]=32141;a[3448]=32143;a[3449]=32159;a[3450]=32173;
a[3451]=32183;a[3452]=32189;a[3453]=32191;a[3454]=32203;a[3455]=32213;a[3456]=32233;a[3457]=32237;a[3458]=32251;a[3459]=32257;a[3460]=32261;
a[3461]=32297;a[3462]=32299;a[3463]=32303;a[3464]=32309;a[3465]=32321;a[3466]=32323;a[3467]=32327;a[3468]=32341;a[3469]=32353;a[3470]=32359;
a[3471]=32363;a[3472]=32369;a[3473]=32371;a[3474]=32377;a[3475]=32381;a[3476]=32401;a[3477]=32411;a[3478]=32413;a[3479]=32423;a[3480]=32429;
a[3481]=32441;a[3482]=32443;a[3483]=32467;a[3484]=32479;a[3485]=32491;a[3486]=32497;a[3487]=32503;a[3488]=32507;a[3489]=32531;a[3490]=32533;
a[3491]=32537;a[3492]=32561;a[3493]=32563;a[3494]=32569;a[3495]=32573;a[3496]=32579;a[3497]=32587;a[3498]=32603;a[3499]=32609;a[3500]=32611;
a[3501]=32621;a[3502]=32633;a[3503]=32647;a[3504]=32653;a[3505]=32687;a[3506]=32693;a[3507]=32707;a[3508]=32713;a[3509]=32717;a[3510]=32719;
a[3511]=32749;a[3512]=32771;a[3513]=32779;a[3514]=32783;a[3515]=32789;a[3516]=32797;a[3517]=32801;a[3518]=32803;a[3519]=32831;a[3520]=32833;
a[3521]=32839;a[3522]=32843;a[3523]=32869;a[3524]=32887;a[3525]=32909;a[3526]=32911;a[3527]=32917;a[3528]=32933;a[3529]=32939;a[3530]=32941;
a[3531]=32957;a[3532]=32969;a[3533]=32971;a[3534]=32983;a[3535]=32987;a[3536]=32993;a[3537]=32999;a[3538]=33013;a[3539]=33023;a[3540]=33029;
a[3541]=33037;a[3542]=33049;a[3543]=33053;a[3544]=33071;a[3545]=33073;a[3546]=33083;a[3547]=33091;a[3548]=33107;a[3549]=33113;a[3550]=33119;
a[3551]=33149;a[3552]=33151;a[3553]=33161;a[3554]=33179;a[3555]=33181;a[3556]=33191;a[3557]=33199;a[3558]=33203;a[3559]=33211;a[3560]=33223;
a[3561]=33247;a[3562]=33287;a[3563]=33289;a[3564]=33301;a[3565]=33311;a[3566]=33317;a[3567]=33329;a[3568]=33331;a[3569]=33343;a[3570]=33347;
a[3571]=33349;a[3572]=33353;a[3573]=33359;a[3574]=33377;a[3575]=33391;a[3576]=33403;a[3577]=33409;a[3578]=33413;a[3579]=33427;a[3580]=33457;
a[3581]=33461;a[3582]=33469;a[3583]=33479;a[3584]=33487;a[3585]=33493;a[3586]=33503;a[3587]=33521;a[3588]=33529;a[3589]=33533;a[3590]=33547;
a[3591]=33563;a[3592]=33569;a[3593]=33577;a[3594]=33581;a[3595]=33587;a[3596]=33589;a[3597]=33599;a[3598]=33601;a[3599]=33613;a[3600]=33617;
a[3601]=33619;a[3602]=33623;a[3603]=33629;a[3604]=33637;a[3605]=33641;a[3606]=33647;a[3607]=33679;a[3608]=33703;a[3609]=33713;a[3610]=33721;
a[3611]=33739;a[3612]=33749;a[3613]=33751;a[3614]=33757;a[3615]=33767;a[3616]=33769;a[3617]=33773;a[3618]=33791;a[3619]=33797;a[3620]=33809;
a[3621]=33811;a[3622]=33827;a[3623]=33829;a[3624]=33851;a[3625]=33857;a[3626]=33863;a[3627]=33871;a[3628]=33889;a[3629]=33893;a[3630]=33911;
a[3631]=33923;a[3632]=33931;a[3633]=33937;a[3634]=33941;a[3635]=33961;a[3636]=33967;a[3637]=33997;a[3638]=34019;a[3639]=34031;a[3640]=34033;
a[3641]=34039;a[3642]=34057;a[3643]=34061;a[3644]=34123;a[3645]=34127;a[3646]=34129;a[3647]=34141;a[3648]=34147;a[3649]=34157;a[3650]=34159;
a[3651]=34171;a[3652]=34183;a[3653]=34211;a[3654]=34213;a[3655]=34217;a[3656]=34231;a[3657]=34253;a[3658]=34259;a[3659]=34261;a[3660]=34267;
a[3661]=34273;a[3662]=34283;a[3663]=34297;a[3664]=34301;a[3665]=34303;a[3666]=34313;a[3667]=34319;a[3668]=34327;a[3669]=34337;a[3670]=34351;
a[3671]=34361;a[3672]=34367;a[3673]=34369;a[3674]=34381;a[3675]=34403;a[3676]=34421;a[3677]=34429;a[3678]=34439;a[3679]=34457;a[3680]=34469;
a[3681]=34471;a[3682]=34483;a[3683]=34487;a[3684]=34499;a[3685]=34501;a[3686]=34511;a[3687]=34513;a[3688]=34519;a[3689]=34537;a[3690]=34543;
a[3691]=34549;a[3692]=34583;a[3693]=34589;a[3694]=34591;a[3695]=34603;a[3696]=34607;a[3697]=34613;a[3698]=34631;a[3699]=34649;a[3700]=34651;
a[3701]=34667;a[3702]=34673;a[3703]=34679;a[3704]=34687;a[3705]=34693;a[3706]=34703;a[3707]=34721;a[3708]=34729;a[3709]=34739;a[3710]=34747;
a[3711]=34757;a[3712]=34759;a[3713]=34763;a[3714]=34781;a[3715]=34807;a[3716]=34819;a[3717]=34841;a[3718]=34843;a[3719]=34847;a[3720]=34849;
a[3721]=34871;a[3722]=34877;a[3723]=34883;a[3724]=34897;a[3725]=34913;a[3726]=34919;a[3727]=34939;a[3728]=34949;a[3729]=34961;a[3730]=34963;
a[3731]=34981;a[3732]=35023;a[3733]=35027;a[3734]=35051;a[3735]=35053;a[3736]=35059;a[3737]=35069;a[3738]=35081;a[3739]=35083;a[3740]=35089;
a[3741]=35099;a[3742]=35107;a[3743]=35111;a[3744]=35117;a[3745]=35129;a[3746]=35141;a[3747]=35149;a[3748]=35153;a[3749]=35159;a[3750]=35171;
a[3751]=35201;a[3752]=35221;a[3753]=35227;a[3754]=35251;a[3755]=35257;a[3756]=35267;a[3757]=35279;a[3758]=35281;a[3759]=35291;a[3760]=35311;
a[3761]=35317;a[3762]=35323;a[3763]=35327;a[3764]=35339;a[3765]=35353;a[3766]=35363;a[3767]=35381;a[3768]=35393;a[3769]=35401;a[3770]=35407;
a[3771]=35419;a[3772]=35423;a[3773]=35437;a[3774]=35447;a[3775]=35449;a[3776]=35461;a[3777]=35491;a[3778]=35507;a[3779]=35509;a[3780]=35521;
a[3781]=35527;a[3782]=35531;a[3783]=35533;a[3784]=35537;a[3785]=35543;a[3786]=35569;a[3787]=35573;a[3788]=35591;a[3789]=35593;a[3790]=35597;
a[3791]=35603;a[3792]=35617;a[3793]=35671;a[3794]=35677;a[3795]=35729;a[3796]=35731;a[3797]=35747;a[3798]=35753;a[3799]=35759;a[3800]=35771;
a[3801]=35797;a[3802]=35801;a[3803]=35803;a[3804]=35809;a[3805]=35831;a[3806]=35837;a[3807]=35839;a[3808]=35851;a[3809]=35863;a[3810]=35869;
a[3811]=35879;a[3812]=35897;a[3813]=35899;a[3814]=35911;a[3815]=35923;a[3816]=35933;a[3817]=35951;a[3818]=35963;a[3819]=35969;a[3820]=35977;
a[3821]=35983;a[3822]=35993;a[3823]=35999;a[3824]=36007;a[3825]=36011;a[3826]=36013;a[3827]=36017;a[3828]=36037;a[3829]=36061;a[3830]=36067;
a[3831]=36073;a[3832]=36083;a[3833]=36097;a[3834]=36107;a[3835]=36109;a[3836]=36131;a[3837]=36137;a[3838]=36151;a[3839]=36161;a[3840]=36187;
a[3841]=36191;a[3842]=36209;a[3843]=36217;a[3844]=36229;a[3845]=36241;a[3846]=36251;a[3847]=36263;a[3848]=36269;a[3849]=36277;a[3850]=36293;
a[3851]=36299;a[3852]=36307;a[3853]=36313;a[3854]=36319;a[3855]=36341;a[3856]=36343;a[3857]=36353;a[3858]=36373;a[3859]=36383;a[3860]=36389;
a[3861]=36433;a[3862]=36451;a[3863]=36457;a[3864]=36467;a[3865]=36469;a[3866]=36473;a[3867]=36479;a[3868]=36493;a[3869]=36497;a[3870]=36523;
a[3871]=36527;a[3872]=36529;a[3873]=36541;a[3874]=36551;a[3875]=36559;a[3876]=36563;a[3877]=36571;a[3878]=36583;a[3879]=36587;a[3880]=36599;
a[3881]=36607;a[3882]=36629;a[3883]=36637;a[3884]=36643;a[3885]=36653;a[3886]=36671;a[3887]=36677;a[3888]=36683;a[3889]=36691;a[3890]=36697;
a[3891]=36709;a[3892]=36713;a[3893]=36721;a[3894]=36739;a[3895]=36749;a[3896]=36761;a[3897]=36767;a[3898]=36779;a[3899]=36781;a[3900]=36787;
a[3901]=36791;a[3902]=36793;a[3903]=36809;a[3904]=36821;a[3905]=36833;a[3906]=36847;a[3907]=36857;a[3908]=36871;a[3909]=36877;a[3910]=36887;
a[3911]=36899;a[3912]=36901;a[3913]=36913;a[3914]=36919;a[3915]=36923;a[3916]=36929;a[3917]=36931;a[3918]=36943;a[3919]=36947;a[3920]=36973;
a[3921]=36979;a[3922]=36997;a[3923]=37003;a[3924]=37013;a[3925]=37019;a[3926]=37021;a[3927]=37039;a[3928]=37049;a[3929]=37057;a[3930]=37061;
a[3931]=37087;a[3932]=37097;a[3933]=37117;a[3934]=37123;a[3935]=37139;a[3936]=37159;a[3937]=37171;a[3938]=37181;a[3939]=37189;a[3940]=37199;
a[3941]=37201;a[3942]=37217;a[3943]=37223;a[3944]=37243;a[3945]=37253;a[3946]=37273;a[3947]=37277;a[3948]=37307;a[3949]=37309;a[3950]=37313;
a[3951]=37321;a[3952]=37337;a[3953]=37339;a[3954]=37357;a[3955]=37361;a[3956]=37363;a[3957]=37369;a[3958]=37379;a[3959]=37397;a[3960]=37409;
a[3961]=37423;a[3962]=37441;a[3963]=37447;a[3964]=37463;a[3965]=37483;a[3966]=37489;a[3967]=37493;a[3968]=37501;a[3969]=37507;a[3970]=37511;
a[3971]=37517;a[3972]=37529;a[3973]=37537;a[3974]=37547;a[3975]=37549;a[3976]=37561;a[3977]=37567;a[3978]=37571;a[3979]=37573;a[3980]=37579;
a[3981]=37589;a[3982]=37591;a[3983]=37607;a[3984]=37619;a[3985]=37633;a[3986]=37643;a[3987]=37649;a[3988]=37657;a[3989]=37663;a[3990]=37691;
a[3991]=37693;a[3992]=37699;a[3993]=37717;a[3994]=37747;a[3995]=37781;a[3996]=37783;a[3997]=37799;a[3998]=37811;a[3999]=37813;a[4000]=37831;
a[4001]=37847;a[4002]=37853;a[4003]=37861;a[4004]=37871;a[4005]=37879;a[4006]=37889;a[4007]=37897;a[4008]=37907;a[4009]=37951;a[4010]=37957;
a[4011]=37963;a[4012]=37967;a[4013]=37987;a[4014]=37991;a[4015]=37993;a[4016]=37997;a[4017]=38011;a[4018]=38039;a[4019]=38047;a[4020]=38053;
a[4021]=38069;a[4022]=38083;a[4023]=38113;a[4024]=38119;a[4025]=38149;a[4026]=38153;a[4027]=38167;a[4028]=38177;a[4029]=38183;a[4030]=38189;
a[4031]=38197;a[4032]=38201;a[4033]=38219;a[4034]=38231;a[4035]=38237;a[4036]=38239;a[4037]=38261;a[4038]=38273;a[4039]=38281;a[4040]=38287;
a[4041]=38299;a[4042]=38303;a[4043]=38317;a[4044]=38321;a[4045]=38327;a[4046]=38329;a[4047]=38333;a[4048]=38351;a[4049]=38371;a[4050]=38377;
a[4051]=38393;a[4052]=38431;a[4053]=38447;a[4054]=38449;a[4055]=38453;a[4056]=38459;a[4057]=38461;a[4058]=38501;a[4059]=38543;a[4060]=38557;
a[4061]=38561;a[4062]=38567;a[4063]=38569;a[4064]=38593;a[4065]=38603;a[4066]=38609;a[4067]=38611;a[4068]=38629;a[4069]=38639;a[4070]=38651;
a[4071]=38653;a[4072]=38669;a[4073]=38671;a[4074]=38677;a[4075]=38693;a[4076]=38699;a[4077]=38707;a[4078]=38711;a[4079]=38713;a[4080]=38723;
a[4081]=38729;a[4082]=38737;a[4083]=38747;a[4084]=38749;a[4085]=38767;a[4086]=38783;a[4087]=38791;a[4088]=38803;a[4089]=38821;a[4090]=38833;
a[4091]=38839;a[4092]=38851;a[4093]=38861;a[4094]=38867;a[4095]=38873;a[4096]=38891;a[4097]=38903;a[4098]=38917;a[4099]=38921;a[4100]=38923;
a[4101]=38933;a[4102]=38953;a[4103]=38959;a[4104]=38971;a[4105]=38977;a[4106]=38993;a[4107]=39019;a[4108]=39023;a[4109]=39041;a[4110]=39043;
a[4111]=39047;a[4112]=39079;a[4113]=39089;a[4114]=39097;a[4115]=39103;a[4116]=39107;a[4117]=39113;a[4118]=39119;a[4119]=39133;a[4120]=39139;
a[4121]=39157;a[4122]=39161;a[4123]=39163;a[4124]=39181;a[4125]=39191;a[4126]=39199;a[4127]=39209;a[4128]=39217;a[4129]=39227;a[4130]=39229;
a[4131]=39233;a[4132]=39239;a[4133]=39241;a[4134]=39251;a[4135]=39293;a[4136]=39301;a[4137]=39313;a[4138]=39317;a[4139]=39323;a[4140]=39341;
a[4141]=39343;a[4142]=39359;a[4143]=39367;a[4144]=39371;a[4145]=39373;a[4146]=39383;a[4147]=39397;a[4148]=39409;a[4149]=39419;a[4150]=39439;
a[4151]=39443;a[4152]=39451;a[4153]=39461;a[4154]=39499;a[4155]=39503;a[4156]=39509;a[4157]=39511;a[4158]=39521;a[4159]=39541;a[4160]=39551;
a[4161]=39563;a[4162]=39569;a[4163]=39581;a[4164]=39607;a[4165]=39619;a[4166]=39623;a[4167]=39631;a[4168]=39659;a[4169]=39667;a[4170]=39671;
a[4171]=39679;a[4172]=39703;a[4173]=39709;a[4174]=39719;a[4175]=39727;a[4176]=39733;a[4177]=39749;a[4178]=39761;a[4179]=39769;a[4180]=39779;
a[4181]=39791;a[4182]=39799;a[4183]=39821;a[4184]=39827;a[4185]=39829;a[4186]=39839;a[4187]=39841;a[4188]=39847;a[4189]=39857;a[4190]=39863;
a[4191]=39869;a[4192]=39877;a[4193]=39883;a[4194]=39887;a[4195]=39901;a[4196]=39929;a[4197]=39937;a[4198]=39953;a[4199]=39971;a[4200]=39979;
a[4201]=39983;a[4202]=39989;a[4203]=40009;a[4204]=40013;a[4205]=40031;a[4206]=40037;a[4207]=40039;a[4208]=40063;a[4209]=40087;a[4210]=40093;
a[4211]=40099;a[4212]=40111;a[4213]=40123;a[4214]=40127;a[4215]=40129;a[4216]=40151;a[4217]=40153;a[4218]=40163;a[4219]=40169;a[4220]=40177;
a[4221]=40189;a[4222]=40193;a[4223]=40213;a[4224]=40231;a[4225]=40237;a[4226]=40241;a[4227]=40253;a[4228]=40277;a[4229]=40283;a[4230]=40289;
a[4231]=40343;a[4232]=40351;a[4233]=40357;a[4234]=40361;a[4235]=40387;a[4236]=40423;a[4237]=40427;a[4238]=40429;a[4239]=40433;a[4240]=40459;
a[4241]=40471;a[4242]=40483;a[4243]=40487;a[4244]=40493;a[4245]=40499;a[4246]=40507;a[4247]=40519;a[4248]=40529;a[4249]=40531;a[4250]=40543;
a[4251]=40559;a[4252]=40577;a[4253]=40583;a[4254]=40591;a[4255]=40597;a[4256]=40609;a[4257]=40627;a[4258]=40637;a[4259]=40639;a[4260]=40693;
a[4261]=40697;a[4262]=40699;a[4263]=40709;a[4264]=40739;a[4265]=40751;a[4266]=40759;a[4267]=40763;a[4268]=40771;a[4269]=40787;a[4270]=40801;
a[4271]=40813;a[4272]=40819;a[4273]=40823;a[4274]=40829;a[4275]=40841;a[4276]=40847;a[4277]=40849;a[4278]=40853;a[4279]=40867;a[4280]=40879;
a[4281]=40883;a[4282]=40897;a[4283]=40903;a[4284]=40927;a[4285]=40933;a[4286]=40939;a[4287]=40949;a[4288]=40961;a[4289]=40973;a[4290]=40993;
a[4291]=41011;a[4292]=41017;a[4293]=41023;a[4294]=41039;a[4295]=41047;a[4296]=41051;a[4297]=41057;a[4298]=41077;a[4299]=41081;a[4300]=41113;
a[4301]=41117;a[4302]=41131;a[4303]=41141;a[4304]=41143;a[4305]=41149;a[4306]=41161;a[4307]=41177;a[4308]=41179;a[4309]=41183;a[4310]=41189;
a[4311]=41201;a[4312]=41203;a[4313]=41213;a[4314]=41221;a[4315]=41227;a[4316]=41231;a[4317]=41233;a[4318]=41243;a[4319]=41257;a[4320]=41263;
a[4321]=41269;a[4322]=41281;a[4323]=41299;a[4324]=41333;a[4325]=41341;a[4326]=41351;a[4327]=41357;a[4328]=41381;a[4329]=41387;a[4330]=41389;
a[4331]=41399;a[4332]=41411;a[4333]=41413;a[4334]=41443;a[4335]=41453;a[4336]=41467;a[4337]=41479;a[4338]=41491;a[4339]=41507;a[4340]=41513;
a[4341]=41519;a[4342]=41521;a[4343]=41539;a[4344]=41543;a[4345]=41549;a[4346]=41579;a[4347]=41593;a[4348]=41597;a[4349]=41603;a[4350]=41609;
a[4351]=41611;a[4352]=41617;a[4353]=41621;a[4354]=41627;a[4355]=41641;a[4356]=41647;a[4357]=41651;a[4358]=41659;a[4359]=41669;a[4360]=41681;
a[4361]=41687;a[4362]=41719;a[4363]=41729;a[4364]=41737;a[4365]=41759;a[4366]=41761;a[4367]=41771;a[4368]=41777;a[4369]=41801;a[4370]=41809;
a[4371]=41813;a[4372]=41843;a[4373]=41849;a[4374]=41851;a[4375]=41863;a[4376]=41879;a[4377]=41887;a[4378]=41893;a[4379]=41897;a[4380]=41903;
a[4381]=41911;a[4382]=41927;a[4383]=41941;a[4384]=41947;a[4385]=41953;a[4386]=41957;a[4387]=41959;a[4388]=41969;a[4389]=41981;a[4390]=41983;
a[4391]=41999;a[4392]=42013;a[4393]=42017;a[4394]=42019;a[4395]=42023;a[4396]=42043;a[4397]=42061;a[4398]=42071;a[4399]=42073;a[4400]=42083;
a[4401]=42089;a[4402]=42101;a[4403]=42131;a[4404]=42139;a[4405]=42157;a[4406]=42169;a[4407]=42179;a[4408]=42181;a[4409]=42187;a[4410]=42193;
a[4411]=42197;a[4412]=42209;a[4413]=42221;a[4414]=42223;a[4415]=42227;a[4416]=42239;a[4417]=42257;a[4418]=42281;a[4419]=42283;a[4420]=42293;
a[4421]=42299;a[4422]=42307;a[4423]=42323;a[4424]=42331;a[4425]=42337;a[4426]=42349;a[4427]=42359;a[4428]=42373;a[4429]=42379;a[4430]=42391;
a[4431]=42397;a[4432]=42403;a[4433]=42407;a[4434]=42409;a[4435]=42433;a[4436]=42437;a[4437]=42443;a[4438]=42451;a[4439]=42457;a[4440]=42461;
a[4441]=42463;a[4442]=42467;a[4443]=42473;a[4444]=42487;a[4445]=42491;a[4446]=42499;a[4447]=42509;a[4448]=42533;a[4449]=42557;a[4450]=42569;
a[4451]=42571;a[4452]=42577;a[4453]=42589;a[4454]=42611;a[4455]=42641;a[4456]=42643;a[4457]=42649;a[4458]=42667;a[4459]=42677;a[4460]=42683;
a[4461]=42689;a[4462]=42697;a[4463]=42701;a[4464]=42703;a[4465]=42709;a[4466]=42719;a[4467]=42727;a[4468]=42737;a[4469]=42743;a[4470]=42751;
a[4471]=42767;a[4472]=42773;a[4473]=42787;a[4474]=42793;a[4475]=42797;a[4476]=42821;a[4477]=42829;a[4478]=42839;a[4479]=42841;a[4480]=42853;
a[4481]=42859;a[4482]=42863;a[4483]=42899;a[4484]=42901;a[4485]=42923;a[4486]=42929;a[4487]=42937;a[4488]=42943;a[4489]=42953;a[4490]=42961;
a[4491]=42967;a[4492]=42979;a[4493]=42989;a[4494]=43003;a[4495]=43013;a[4496]=43019;a[4497]=43037;a[4498]=43049;a[4499]=43051;a[4500]=43063;
a[4501]=43067;a[4502]=43093;a[4503]=43103;a[4504]=43117;a[4505]=43133;a[4506]=43151;a[4507]=43159;a[4508]=43177;a[4509]=43189;a[4510]=43201;
a[4511]=43207;a[4512]=43223;a[4513]=43237;a[4514]=43261;a[4515]=43271;a[4516]=43283;a[4517]=43291;a[4518]=43313;a[4519]=43319;a[4520]=43321;
a[4521]=43331;a[4522]=43391;a[4523]=43397;a[4524]=43399;a[4525]=43403;a[4526]=43411;a[4527]=43427;a[4528]=43441;a[4529]=43451;a[4530]=43457;
a[4531]=43481;a[4532]=43487;a[4533]=43499;a[4534]=43517;a[4535]=43541;a[4536]=43543;a[4537]=43573;a[4538]=43577;a[4539]=43579;a[4540]=43591;
a[4541]=43597;a[4542]=43607;a[4543]=43609;a[4544]=43613;a[4545]=43627;a[4546]=43633;a[4547]=43649;a[4548]=43651;a[4549]=43661;a[4550]=43669;
a[4551]=43691;a[4552]=43711;a[4553]=43717;a[4554]=43721;a[4555]=43753;a[4556]=43759;a[4557]=43777;a[4558]=43781;a[4559]=43783;a[4560]=43787;
a[4561]=43789;a[4562]=43793;a[4563]=43801;a[4564]=43853;a[4565]=43867;a[4566]=43889;a[4567]=43891;a[4568]=43913;a[4569]=43933;a[4570]=43943;
a[4571]=43951;a[4572]=43961;a[4573]=43963;a[4574]=43969;a[4575]=43973;a[4576]=43987;a[4577]=43991;a[4578]=43997;a[4579]=44017;a[4580]=44021;
a[4581]=44027;a[4582]=44029;a[4583]=44041;a[4584]=44053;a[4585]=44059;a[4586]=44071;a[4587]=44087;a[4588]=44089;a[4589]=44101;a[4590]=44111;
a[4591]=44119;a[4592]=44123;a[4593]=44129;a[4594]=44131;a[4595]=44159;a[4596]=44171;a[4597]=44179;a[4598]=44189;a[4599]=44201;a[4600]=44203;
a[4601]=44207;a[4602]=44221;a[4603]=44249;a[4604]=44257;a[4605]=44263;a[4606]=44267;a[4607]=44269;a[4608]=44273;a[4609]=44279;a[4610]=44281;
a[4611]=44293;a[4612]=44351;a[4613]=44357;a[4614]=44371;a[4615]=44381;a[4616]=44383;a[4617]=44389;a[4618]=44417;a[4619]=44449;a[4620]=44453;
a[4621]=44483;a[4622]=44491;a[4623]=44497;a[4624]=44501;a[4625]=44507;a[4626]=44519;a[4627]=44531;a[4628]=44533;a[4629]=44537;a[4630]=44543;
a[4631]=44549;a[4632]=44563;a[4633]=44579;a[4634]=44587;a[4635]=44617;a[4636]=44621;a[4637]=44623;a[4638]=44633;a[4639]=44641;a[4640]=44647;
a[4641]=44651;a[4642]=44657;a[4643]=44683;a[4644]=44687;a[4645]=44699;a[4646]=44701;a[4647]=44711;
 h=fopen("zero2.in","r");l=4647;g=fopen("zero2.out","w");
 for(i=1;i<=10;i++)
  {r=0;for(j=1;j<=30;j++){b[j]=0;c[j]=0;d[j]=0;e[j]=0;f[j]=0;}
   fscanf(h,"%ld%ld",&n,&o);
   for(j=0;j<=l&&o>1;j++)
   if(o%a[j]==0){r++;b[r]=a[j];while(o%a[j]==0){c[r]++;o/=a[j];}}
   if(o>1){r++;b[r]=o;}
   for(j=1;j<=n;j++)
    {q=j;for(k=1;k<=r;k++)e[k]=f[k];
     for(k=1;k<=r;k++)
      {while(q%b[k]==0){f[k]++;q/=b[k];}
       e[k]=f[k];d[k]+=f[k];
      }
    }
   min=2000000000;
   for(k=1;k<=r;k++)if((d[k]/c[k])<min)min=d[k]/c[k];fprintf(g,"%ld\n",min);
  }
  fclose(h);fclose(g);
 return 0;
}