/* bc program perfect_power */ /*NOTE: in bc we have */ /* a%b=m(a,b) if a>=0 or a<0 and b divides a */ /* a%b=m(a,b)-b if a<0, b>0, a not divisible by b */ /* a/b=[a/b] if a>=0 or a<0 and b divides a */ /* a/b=[a/b]+1 if a<0, b>0, a not divisible by b */ /* a=b(a/b)+a%b */ /* mod(a,b)=the least non-negative remainder when an integer a is divided by a positive integer b */ define mod(a,b){ auto c c=a%b if(a>=0) return(c) if(c==0) return(0) return(c+b) } /* int(a,b)=integer part of a/b, a, b integers, b != 0 */ define int(a,b){ if(b<0){ a= -a b= -b } return((a-mod(a,b))/b) } define binary_log(n){ auto i i=0 while(n){ n=n/2 i=i+1 } return(i-1) } define mthroot(a,b,m){ auto s,x,y,i,z,d,j a=a/b if(a==0)return(0) s=a while(s>1){ s=s/2 i=i+1 } x=2^(1+(i/m)) /* print "x[0]=",x,"\n"*/ j=1 while(1){ y=x z=x^(m-1) x=x+int(a-x*z,m*z) /*print "x[",j,"]=",x,"\n"*/ j=j+1 if(y<=x) break } return(y) } prime[0]=2 prime[1]=3 prime[2]=5 prime[3]=7 prime[4]=11 prime[5]=13 prime[6]=17 prime[7]=19 prime[8]=23 prime[9]=29 prime[10]=31 prime[11]=37 prime[12]=41 prime[13]=43 prime[14]=47 prime[15]=53 prime[16]=59 prime[17]=61 prime[18]=67 prime[19]=71 prime[20]=73 prime[21]=79 prime[22]=83 prime[23]=89 prime[24]=97 prime[25]=101 prime[26]=103 prime[27]=107 prime[28]=109 prime[29]=113 prime[30]=127 prime[31]=131 prime[32]=137 prime[33]=139 prime[34]=149 prime[35]=151 prime[36]=157 prime[37]=163 prime[38]=167 prime[39]=173 prime[40]=179 prime[41]=181 prime[42]=191 prime[43]=193 prime[44]=197 prime[45]=199 prime[46]=211 prime[47]=223 prime[48]=227 prime[49]=229 prime[50]=233 prime[51]=239 prime[52]=241 prime[53]=251 prime[54]=257 prime[55]=263 prime[56]=269 prime[57]=271 prime[58]=277 prime[59]=281 prime[60]=283 prime[61]=293 prime[62]=307 prime[63]=311 prime[64]=313 prime[65]=317 prime[66]=331 prime[67]=337 prime[68]=347 prime[69]=349 prime[70]=353 prime[71]=359 prime[72]=367 prime[73]=373 prime[74]=379 prime[75]=383 prime[76]=389 prime[77]=397 prime[78]=401 prime[79]=409 prime[80]=419 prime[81]=421 prime[82]=431 prime[83]=433 prime[84]=439 prime[85]=443 prime[86]=449 prime[87]=457 prime[88]=461 prime[89]=463 prime[90]=467 prime[91]=479 prime[92]=487 prime[93]=491 prime[94]=499 prime[95]=503 prime[96]=509 prime[97]=521 prime[98]=523 prime[99]=541 prime[100]=547 prime[101]=557 prime[102]=563 prime[103]=569 prime[104]=571 prime[105]=577 prime[106]=587 prime[107]=593 prime[108]=599 prime[109]=601 prime[110]=607 prime[111]=613 prime[112]=617 prime[113]=619 prime[114]=631 prime[115]=641 prime[116]=643 prime[117]=647 prime[118]=653 prime[119]=659 prime[120]=661 prime[121]=673 prime[122]=677 prime[123]=683 prime[124]=691 prime[125]=701 prime[126]=709 prime[127]=719 prime[128]=727 prime[129]=733 prime[130]=739 prime[131]=743 prime[132]=751 prime[133]=757 prime[134]=761 prime[135]=769 prime[136]=773 prime[137]=787 prime[138]=797 prime[139]=809 prime[140]=811 prime[141]=821 prime[142]=823 prime[143]=827 prime[144]=829 prime[145]=839 prime[146]=853 prime[147]=857 prime[148]=859 prime[149]=863 prime[150]=877 prime[151]=881 prime[152]=883 prime[153]=887 prime[154]=907 prime[155]=911 prime[156]=919 prime[157]=929 prime[158]=937 prime[159]=941 prime[160]=947 prime[161]=953 prime[162]=967 prime[163]=971 prime[164]=977 prime[165]=983 prime[166]=991 prime[167]=997 prime[168]=1009 prime[169]=1013 prime[170]=1019 prime[171]=1021 prime[172]=1031 prime[173]=1033 prime[174]=1039 prime[175]=1049 prime[176]=1051 prime[177]=1061 prime[178]=1063 prime[179]=1069 prime[180]=1087 prime[181]=1091 prime[182]=1093 prime[183]=1097 prime[184]=1103 prime[185]=1109 prime[186]=1117 prime[187]=1123 prime[188]=1129 prime[189]=1151 prime[190]=1153 prime[191]=1163 prime[192]=1171 prime[193]=1181 prime[194]=1187 prime[195]=1193 prime[196]=1201 prime[197]=1213 prime[198]=1217 prime[199]=1223 prime[200]=1229 prime[201]=1231 prime[202]=1237 prime[203]=1249 prime[204]=1259 prime[205]=1277 prime[206]=1279 prime[207]=1283 prime[208]=1289 prime[209]=1291 prime[210]=1297 prime[211]=1301 prime[212]=1303 prime[213]=1307 prime[214]=1319 prime[215]=1321 prime[216]=1327 prime[217]=1361 prime[218]=1367 prime[219]=1373 prime[220]=1381 prime[221]=1399 prime[222]=1409 prime[223]=1423 prime[224]=1427 prime[225]=1429 prime[226]=1433 prime[227]=1439 prime[228]=1447 prime[229]=1451 prime[230]=1453 prime[231]=1459 prime[232]=1471 prime[233]=1481 prime[234]=1483 prime[235]=1487 prime[236]=1489 prime[237]=1493 prime[238]=1499 prime[239]=1511 prime[240]=1523 prime[241]=1531 prime[242]=1543 prime[243]=1549 prime[244]=1553 prime[245]=1559 prime[246]=1567 prime[247]=1571 prime[248]=1579 prime[249]=1583 prime[250]=1597 prime[251]=1601 prime[252]=1607 prime[253]=1609 prime[254]=1613 prime[255]=1619 prime[256]=1621 prime[257]=1627 prime[258]=1637 prime[259]=1657 prime[260]=1663 prime[261]=1667 prime[262]=1669 prime[263]=1693 prime[264]=1697 prime[265]=1699 prime[266]=1709 prime[267]=1721 prime[268]=1723 prime[269]=1733 prime[270]=1741 prime[271]=1747 prime[272]=1753 prime[273]=1759 prime[274]=1777 prime[275]=1783 prime[276]=1787 prime[277]=1789 prime[278]=1801 prime[279]=1811 prime[280]=1823 prime[281]=1831 prime[282]=1847 prime[283]=1861 prime[284]=1867 prime[285]=1871 prime[286]=1873 prime[287]=1877 prime[288]=1879 prime[289]=1889 prime[290]=1901 prime[291]=1907 prime[292]=1913 prime[293]=1931 prime[294]=1933 prime[295]=1949 prime[296]=1951 prime[297]=1973 prime[298]=1979 prime[299]=1987 prime[300]=1993 prime[301]=1997 prime[302]=1999 prime[303]=2003 prime[304]=2011 prime[305]=2017 prime[306]=2027 prime[307]=2029 prime[308]=2039 prime[309]=2053 prime[310]=2063 prime[311]=2069 prime[312]=2081 prime[313]=2083 prime[314]=2087 prime[315]=2089 prime[316]=2099 prime[317]=2111 prime[318]=2113 prime[319]=2129 prime[320]=2131 prime[321]=2137 prime[322]=2141 prime[323]=2143 prime[324]=2153 prime[325]=2161 prime[326]=2179 prime[327]=2203 prime[328]=2207 prime[329]=2213 prime[330]=2221 prime[331]=2237 prime[332]=2239 prime[333]=2243 prime[334]=2251 prime[335]=2267 prime[336]=2269 prime[337]=2273 prime[338]=2281 prime[339]=2287 prime[340]=2293 prime[341]=2297 prime[342]=2309 prime[343]=2311 prime[344]=2333 prime[345]=2339 prime[346]=2341 prime[347]=2347 prime[348]=2351 prime[349]=2357 prime[350]=2371 prime[351]=2377 prime[352]=2381 prime[353]=2383 prime[354]=2389 prime[355]=2393 prime[356]=2399 prime[357]=2411 prime[358]=2417 prime[359]=2423 prime[360]=2437 prime[361]=2441 prime[362]=2447 prime[363]=2459 prime[364]=2467 prime[365]=2473 prime[366]=2477 prime[367]=2503 prime[368]=2521 prime[369]=2531 prime[370]=2539 prime[371]=2543 prime[372]=2549 prime[373]=2551 prime[374]=2557 prime[375]=2579 prime[376]=2591 prime[377]=2593 prime[378]=2609 prime[379]=2617 prime[380]=2621 prime[381]=2633 prime[382]=2647 prime[383]=2657 prime[384]=2659 prime[385]=2663 prime[386]=2671 prime[387]=2677 prime[388]=2683 prime[389]=2687 prime[390]=2689 prime[391]=2693 prime[392]=2699 prime[393]=2707 prime[394]=2711 prime[395]=2713 prime[396]=2719 prime[397]=2729 prime[398]=2731 prime[399]=2741 prime[400]=2749 prime[401]=2753 prime[402]=2767 prime[403]=2777 prime[404]=2789 prime[405]=2791 prime[406]=2797 prime[407]=2801 prime[408]=2803 prime[409]=2819 prime[410]=2833 prime[411]=2837 prime[412]=2843 prime[413]=2851 prime[414]=2857 prime[415]=2861 prime[416]=2879 prime[417]=2887 prime[418]=2897 prime[419]=2903 prime[420]=2909 prime[421]=2917 prime[422]=2927 prime[423]=2939 prime[424]=2953 prime[425]=2957 prime[426]=2963 prime[427]=2969 prime[428]=2971 prime[429]=2999 prime[430]=3001 prime[431]=3011 prime[432]=3019 prime[433]=3023 prime[434]=3037 prime[435]=3041 prime[436]=3049 prime[437]=3061 prime[438]=3067 prime[439]=3079 prime[440]=3083 prime[441]=3089 prime[442]=3109 prime[443]=3119 prime[444]=3121 prime[445]=3137 prime[446]=3163 prime[447]=3167 prime[448]=3169 prime[449]=3181 prime[450]=3187 prime[451]=3191 prime[452]=3203 prime[453]=3209 prime[454]=3217 prime[455]=3221 prime[456]=3229 prime[457]=3251 prime[458]=3253 prime[459]=3257 prime[460]=3259 prime[461]=3271 prime[462]=3299 prime[463]=3301 prime[464]=3307 prime[465]=3313 prime[466]=3319 prime[467]=3323 prime[468]=3329 prime[469]=3331 prime[470]=3343 prime[471]=3347 prime[472]=3359 prime[473]=3361 prime[474]=3371 prime[475]=3373 prime[476]=3389 prime[477]=3391 prime[478]=3407 prime[479]=3413 prime[480]=3433 prime[481]=3449 prime[482]=3457 prime[483]=3461 prime[484]=3463 prime[485]=3467 prime[486]=3469 prime[487]=3491 prime[488]=3499 prime[489]=3511 prime[490]=3517 prime[491]=3527 prime[492]=3529 prime[493]=3533 prime[494]=3539 prime[495]=3541 prime[496]=3547 prime[497]=3557 prime[498]=3559 prime[499]=3571 prime[500]=3581 prime[501]=3583 prime[502]=3593 prime[503]=3607 prime[504]=3613 prime[505]=3617 prime[506]=3623 prime[507]=3631 prime[508]=3637 prime[509]=3643 prime[510]=3659 prime[511]=3671 prime[512]=3673 prime[513]=3677 prime[514]=3691 prime[515]=3697 prime[516]=3701 prime[517]=3709 prime[518]=3719 prime[519]=3727 prime[520]=3733 prime[521]=3739 prime[522]=3761 prime[523]=3767 prime[524]=3769 prime[525]=3779 prime[526]=3793 prime[527]=3797 prime[528]=3803 prime[529]=3821 prime[530]=3823 prime[531]=3833 prime[532]=3847 prime[533]=3851 prime[534]=3853 prime[535]=3863 prime[536]=3877 prime[537]=3881 prime[538]=3889 prime[539]=3907 prime[540]=3911 prime[541]=3917 prime[542]=3919 prime[543]=3923 prime[544]=3929 prime[545]=3931 prime[546]=3943 prime[547]=3947 prime[548]=3967 prime[549]=3989 prime[550]=4001 prime[551]=4003 prime[552]=4007 prime[553]=4013 prime[554]=4019 prime[555]=4021 prime[556]=4027 prime[557]=4049 prime[558]=4051 prime[559]=4057 prime[560]=4073 prime[561]=4079 prime[562]=4091 prime[563]=4093 prime[564]=4099 prime[565]=4111 prime[566]=4127 prime[567]=4129 prime[568]=4133 prime[569]=4139 prime[570]=4153 prime[571]=4157 prime[572]=4159 prime[573]=4177 prime[574]=4201 prime[575]=4211 prime[576]=4217 prime[577]=4219 prime[578]=4229 prime[579]=4231 prime[580]=4241 prime[581]=4243 prime[582]=4253 prime[583]=4259 prime[584]=4261 prime[585]=4271 prime[586]=4273 prime[587]=4283 prime[588]=4289 prime[589]=4297 prime[590]=4327 prime[591]=4337 prime[592]=4339 prime[593]=4349 prime[594]=4357 prime[595]=4363 prime[596]=4373 prime[597]=4391 prime[598]=4397 prime[599]=4409 prime[600]=4421 prime[601]=4423 prime[602]=4441 prime[603]=4447 prime[604]=4451 prime[605]=4457 prime[606]=4463 prime[607]=4481 prime[608]=4483 prime[609]=4493 prime[610]=4507 prime[611]=4513 prime[612]=4517 prime[613]=4519 prime[614]=4523 prime[615]=4547 prime[616]=4549 prime[617]=4561 prime[618]=4567 prime[619]=4583 prime[620]=4591 prime[621]=4597 prime[622]=4603 prime[623]=4621 prime[624]=4637 prime[625]=4639 prime[626]=4643 prime[627]=4649 prime[628]=4651 prime[629]=4657 prime[630]=4663 prime[631]=4673 prime[632]=4679 prime[633]=4691 prime[634]=4703 prime[635]=4721 prime[636]=4723 prime[637]=4729 prime[638]=4733 prime[639]=4751 prime[640]=4759 prime[641]=4783 prime[642]=4787 prime[643]=4789 prime[644]=4793 prime[645]=4799 prime[646]=4801 prime[647]=4813 prime[648]=4817 prime[649]=4831 prime[650]=4861 prime[651]=4871 prime[652]=4877 prime[653]=4889 prime[654]=4903 prime[655]=4909 prime[656]=4919 prime[657]=4931 prime[658]=4933 prime[659]=4937 prime[660]=4943 prime[661]=4951 prime[662]=4957 prime[663]=4967 prime[664]=4969 prime[665]=4973 prime[666]=4987 prime[667]=4993 prime[668]=4999 prime[669]=5003 prime[670]=5009 prime[671]=5011 prime[672]=5021 prime[673]=5023 prime[674]=5039 prime[675]=5051 prime[676]=5059 prime[677]=5077 prime[678]=5081 prime[679]=5087 prime[680]=5099 prime[681]=5101 prime[682]=5107 prime[683]=5113 prime[684]=5119 prime[685]=5147 prime[686]=5153 prime[687]=5167 prime[688]=5171 prime[689]=5179 prime[690]=5189 prime[691]=5197 prime[692]=5209 prime[693]=5227 prime[694]=5231 prime[695]=5233 prime[696]=5237 prime[697]=5261 prime[698]=5273 prime[699]=5279 prime[700]=5281 prime[701]=5297 prime[702]=5303 prime[703]=5309 prime[704]=5323 prime[705]=5333 prime[706]=5347 prime[707]=5351 prime[708]=5381 prime[709]=5387 prime[710]=5393 prime[711]=5399 prime[712]=5407 prime[713]=5413 prime[714]=5417 prime[715]=5419 prime[716]=5431 prime[717]=5437 prime[718]=5441 prime[719]=5443 prime[720]=5449 prime[721]=5471 prime[722]=5477 prime[723]=5479 prime[724]=5483 prime[725]=5501 prime[726]=5503 prime[727]=5507 prime[728]=5519 prime[729]=5521 prime[730]=5527 prime[731]=5531 prime[732]=5557 prime[733]=5563 prime[734]=5569 prime[735]=5573 prime[736]=5581 prime[737]=5591 prime[738]=5623 prime[739]=5639 prime[740]=5641 prime[741]=5647 prime[742]=5651 prime[743]=5653 prime[744]=5657 prime[745]=5659 prime[746]=5669 prime[747]=5683 prime[748]=5689 prime[749]=5693 prime[750]=5701 prime[751]=5711 prime[752]=5717 prime[753]=5737 prime[754]=5741 prime[755]=5743 prime[756]=5749 prime[757]=5779 prime[758]=5783 prime[759]=5791 prime[760]=5801 prime[761]=5807 prime[762]=5813 prime[763]=5821 prime[764]=5827 prime[765]=5839 prime[766]=5843 prime[767]=5849 prime[768]=5851 prime[769]=5857 prime[770]=5861 prime[771]=5867 prime[772]=5869 prime[773]=5879 prime[774]=5881 prime[775]=5897 prime[776]=5903 prime[777]=5923 prime[778]=5927 prime[779]=5939 prime[780]=5953 prime[781]=5981 prime[782]=5987 prime[783]=6007 prime[784]=6011 prime[785]=6029 prime[786]=6037 prime[787]=6043 prime[788]=6047 prime[789]=6053 prime[790]=6067 prime[791]=6073 prime[792]=6079 prime[793]=6089 prime[794]=6091 prime[795]=6101 prime[796]=6113 prime[797]=6121 prime[798]=6131 prime[799]=6133 prime[800]=6143 prime[801]=6151 prime[802]=6163 prime[803]=6173 prime[804]=6197 prime[805]=6199 prime[806]=6203 prime[807]=6211 prime[808]=6217 prime[809]=6221 prime[810]=6229 prime[811]=6247 prime[812]=6257 prime[813]=6263 prime[814]=6269 prime[815]=6271 prime[816]=6277 prime[817]=6287 prime[818]=6299 prime[819]=6301 prime[820]=6311 prime[821]=6317 prime[822]=6323 prime[823]=6329 prime[824]=6337 prime[825]=6343 prime[826]=6353 prime[827]=6359 prime[828]=6361 prime[829]=6367 prime[830]=6373 prime[831]=6379 prime[832]=6389 prime[833]=6397 prime[834]=6421 prime[835]=6427 prime[836]=6449 prime[837]=6451 prime[838]=6469 prime[839]=6473 prime[840]=6481 prime[841]=6491 prime[842]=6521 prime[843]=6529 prime[844]=6547 prime[845]=6551 prime[846]=6553 prime[847]=6563 prime[848]=6569 prime[849]=6571 prime[850]=6577 prime[851]=6581 prime[852]=6599 prime[853]=6607 prime[854]=6619 prime[855]=6637 prime[856]=6653 prime[857]=6659 prime[858]=6661 prime[859]=6673 prime[860]=6679 prime[861]=6689 prime[862]=6691 prime[863]=6701 prime[864]=6703 prime[865]=6709 prime[866]=6719 prime[867]=6733 prime[868]=6737 prime[869]=6761 prime[870]=6763 prime[871]=6779 prime[872]=6781 prime[873]=6791 prime[874]=6793 prime[875]=6803 prime[876]=6823 prime[877]=6827 prime[878]=6829 prime[879]=6833 prime[880]=6841 prime[881]=6857 prime[882]=6863 prime[883]=6869 prime[884]=6871 prime[885]=6883 prime[886]=6899 prime[887]=6907 prime[888]=6911 prime[889]=6917 prime[890]=6947 prime[891]=6949 prime[892]=6959 prime[893]=6961 prime[894]=6967 prime[895]=6971 prime[896]=6977 prime[897]=6983 prime[898]=6991 prime[899]=6997 prime[900]=7001 prime[901]=7013 prime[902]=7019 prime[903]=7027 prime[904]=7039 prime[905]=7043 prime[906]=7057 prime[907]=7069 prime[908]=7079 prime[909]=7103 prime[910]=7109 prime[911]=7121 prime[912]=7127 prime[913]=7129 prime[914]=7151 prime[915]=7159 prime[916]=7177 prime[917]=7187 prime[918]=7193 prime[919]=7207 prime[920]=7211 prime[921]=7213 prime[922]=7219 prime[923]=7229 prime[924]=7237 prime[925]=7243 prime[926]=7247 prime[927]=7253 prime[928]=7283 prime[929]=7297 prime[930]=7307 prime[931]=7309 prime[932]=7321 prime[933]=7331 prime[934]=7333 prime[935]=7349 prime[936]=7351 prime[937]=7369 prime[938]=7393 prime[939]=7411 prime[940]=7417 prime[941]=7433 prime[942]=7451 prime[943]=7457 prime[944]=7459 prime[945]=7477 prime[946]=7481 prime[947]=7487 prime[948]=7489 prime[949]=7499 prime[950]=7507 prime[951]=7517 prime[952]=7523 prime[953]=7529 prime[954]=7537 prime[955]=7541 prime[956]=7547 prime[957]=7549 prime[958]=7559 prime[959]=7561 prime[960]=7573 prime[961]=7577 prime[962]=7583 prime[963]=7589 prime[964]=7591 prime[965]=7603 prime[966]=7607 prime[967]=7621 prime[968]=7639 prime[969]=7643 prime[970]=7649 prime[971]=7669 prime[972]=7673 prime[973]=7681 prime[974]=7687 prime[975]=7691 prime[976]=7699 prime[977]=7703 prime[978]=7717 prime[979]=7723 prime[980]=7727 prime[981]=7741 prime[982]=7753 prime[983]=7757 prime[984]=7759 prime[985]=7789 prime[986]=7793 prime[987]=7817 prime[988]=7823 prime[989]=7829 prime[990]=7841 prime[991]=7853 prime[992]=7867 prime[993]=7873 prime[994]=7877 prime[995]=7879 prime[996]=7883 prime[997]=7901 prime[998]=7907 prime[999]=7919 prime[1000]=7927 prime[1001]=7933 prime[1002]=7937 prime[1003]=7949 prime[1004]=7951 prime[1005]=7963 prime[1006]=7993 prime[1007]=8009 prime[1008]=8011 prime[1009]=8017 prime[1010]=8039 prime[1011]=8053 prime[1012]=8059 prime[1013]=8069 prime[1014]=8081 prime[1015]=8087 prime[1016]=8089 prime[1017]=8093 prime[1018]=8101 prime[1019]=8111 prime[1020]=8117 prime[1021]=8123 prime[1022]=8147 prime[1023]=8161 prime[1024]=8167 prime[1025]=8171 prime[1026]=8179 prime[1027]=8191 prime[1028]=8209 prime[1029]=8219 prime[1030]=8221 prime[1031]=8231 prime[1032]=8233 prime[1033]=8237 prime[1034]=8243 prime[1035]=8263 prime[1036]=8269 prime[1037]=8273 prime[1038]=8287 prime[1039]=8291 prime[1040]=8293 prime[1041]=8297 prime[1042]=8311 prime[1043]=8317 prime[1044]=8329 prime[1045]=8353 prime[1046]=8363 prime[1047]=8369 prime[1048]=8377 prime[1049]=8387 prime[1050]=8389 prime[1051]=8419 prime[1052]=8423 prime[1053]=8429 prime[1054]=8431 prime[1055]=8443 prime[1056]=8447 prime[1057]=8461 prime[1058]=8467 prime[1059]=8501 prime[1060]=8513 prime[1061]=8521 prime[1062]=8527 prime[1063]=8537 prime[1064]=8539 prime[1065]=8543 prime[1066]=8563 prime[1067]=8573 prime[1068]=8581 prime[1069]=8597 prime[1070]=8599 prime[1071]=8609 prime[1072]=8623 prime[1073]=8627 prime[1074]=8629 prime[1075]=8641 prime[1076]=8647 prime[1077]=8663 prime[1078]=8669 prime[1079]=8677 prime[1080]=8681 prime[1081]=8689 prime[1082]=8693 prime[1083]=8699 prime[1084]=8707 prime[1085]=8713 prime[1086]=8719 prime[1087]=8731 prime[1088]=8737 prime[1089]=8741 prime[1090]=8747 prime[1091]=8753 prime[1092]=8761 prime[1093]=8779 prime[1094]=8783 prime[1095]=8803 prime[1096]=8807 prime[1097]=8819 prime[1098]=8821 prime[1099]=8831 prime[1100]=8837 prime[1101]=8839 prime[1102]=8849 prime[1103]=8861 prime[1104]=8863 prime[1105]=8867 prime[1106]=8887 prime[1107]=8893 prime[1108]=8923 prime[1109]=8929 prime[1110]=8933 prime[1111]=8941 prime[1112]=8951 prime[1113]=8963 prime[1114]=8969 prime[1115]=8971 prime[1116]=8999 prime[1117]=9001 prime[1118]=9007 prime[1119]=9011 prime[1120]=9013 prime[1121]=9029 prime[1122]=9041 prime[1123]=9043 prime[1124]=9049 prime[1125]=9059 prime[1126]=9067 prime[1127]=9091 prime[1128]=9103 prime[1129]=9109 prime[1130]=9127 prime[1131]=9133 prime[1132]=9137 prime[1133]=9151 prime[1134]=9157 prime[1135]=9161 prime[1136]=9173 prime[1137]=9181 prime[1138]=9187 prime[1139]=9199 prime[1140]=9203 prime[1141]=9209 prime[1142]=9221 prime[1143]=9227 prime[1144]=9239 prime[1145]=9241 prime[1146]=9257 prime[1147]=9277 prime[1148]=9281 prime[1149]=9283 prime[1150]=9293 prime[1151]=9311 prime[1152]=9319 prime[1153]=9323 prime[1154]=9337 prime[1155]=9341 prime[1156]=9343 prime[1157]=9349 prime[1158]=9371 prime[1159]=9377 prime[1160]=9391 prime[1161]=9397 prime[1162]=9403 prime[1163]=9413 prime[1164]=9419 prime[1165]=9421 prime[1166]=9431 prime[1167]=9433 prime[1168]=9437 prime[1169]=9439 prime[1170]=9461 prime[1171]=9463 prime[1172]=9467 prime[1173]=9473 prime[1174]=9479 prime[1175]=9491 prime[1176]=9497 prime[1177]=9511 prime[1178]=9521 prime[1179]=9533 prime[1180]=9539 prime[1181]=9547 prime[1182]=9551 prime[1183]=9587 prime[1184]=9601 prime[1185]=9613 prime[1186]=9619 prime[1187]=9623 prime[1188]=9629 prime[1189]=9631 prime[1190]=9643 prime[1191]=9649 prime[1192]=9661 prime[1193]=9677 prime[1194]=9679 prime[1195]=9689 prime[1196]=9697 prime[1197]=9719 prime[1198]=9721 prime[1199]=9733 prime[1200]=9739 prime[1201]=9743 prime[1202]=9749 prime[1203]=9767 prime[1204]=9769 prime[1205]=9781 prime[1206]=9787 prime[1207]=9791 prime[1208]=9803 prime[1209]=9811 prime[1210]=9817 prime[1211]=9829 prime[1212]=9833 prime[1213]=9839 prime[1214]=9851 prime[1215]=9857 prime[1216]=9859 prime[1217]=9871 prime[1218]=9883 prime[1219]=9887 prime[1220]=9901 prime[1221]=9907 prime[1222]=9923 prime[1223]=9929 prime[1224]=9931 prime[1225]=9941 prime[1226]=9949 prime[1227]=9967 prime[1228]=9973 prime[1229]=10007 prime[1230]=10009 prime[1231]=10037 prime[1232]=10039 prime[1233]=10061 prime[1234]=10067 prime[1235]=10069 prime[1236]=10079 prime[1237]=10091 prime[1238]=10093 prime[1239]=10099 prime[1240]=10103 prime[1241]=10111 prime[1242]=10133 prime[1243]=10139 prime[1244]=10141 prime[1245]=10151 prime[1246]=10159 prime[1247]=10163 prime[1248]=10169 prime[1249]=10177 prime[1250]=10181 prime[1251]=10193 prime[1252]=10211 prime[1253]=10223 prime[1254]=10243 prime[1255]=10247 prime[1256]=10253 prime[1257]=10259 prime[1258]=10267 prime[1259]=10271 prime[1260]=10273 prime[1261]=10289 prime[1262]=10301 prime[1263]=10303 prime[1264]=10313 prime[1265]=10321 prime[1266]=10331 prime[1267]=10333 prime[1268]=10337 prime[1269]=10343 prime[1270]=10357 prime[1271]=10369 prime[1272]=10391 prime[1273]=10399 prime[1274]=10427 prime[1275]=10429 prime[1276]=10433 prime[1277]=10453 prime[1278]=10457 prime[1279]=10459 prime[1280]=10463 prime[1281]=10477 prime[1282]=10487 prime[1283]=10499 prime[1284]=10501 prime[1285]=10513 prime[1286]=10529 prime[1287]=10531 prime[1288]=10559 prime[1289]=10567 prime[1290]=10589 prime[1291]=10597 prime[1292]=10601 prime[1293]=10607 prime[1294]=10613 prime[1295]=10627 prime[1296]=10631 prime[1297]=10639 prime[1298]=10651 prime[1299]=10657 prime[1300]=10663 prime[1301]=10667 prime[1302]=10687 prime[1303]=10691 prime[1304]=10709 prime[1305]=10711 prime[1306]=10723 prime[1307]=10729 prime[1308]=10733 prime[1309]=10739 prime[1310]=10753 prime[1311]=10771 prime[1312]=10781 prime[1313]=10789 prime[1314]=10799 prime[1315]=10831 prime[1316]=10837 prime[1317]=10847 prime[1318]=10853 prime[1319]=10859 prime[1320]=10861 prime[1321]=10867 prime[1322]=10883 prime[1323]=10889 prime[1324]=10891 prime[1325]=10903 prime[1326]=10909 prime[1327]=10937 prime[1328]=10939 prime[1329]=10949 prime[1330]=10957 prime[1331]=10973 prime[1332]=10979 prime[1333]=10987 prime[1334]=10993 prime[1335]=11003 prime[1336]=11027 prime[1337]=11047 prime[1338]=11057 prime[1339]=11059 prime[1340]=11069 prime[1341]=11071 prime[1342]=11083 prime[1343]=11087 prime[1344]=11093 prime[1345]=11113 prime[1346]=11117 prime[1347]=11119 prime[1348]=11131 prime[1349]=11149 prime[1350]=11159 prime[1351]=11161 prime[1352]=11171 prime[1353]=11173 prime[1354]=11177 prime[1355]=11197 prime[1356]=11213 prime[1357]=11239 prime[1358]=11243 prime[1359]=11251 prime[1360]=11257 prime[1361]=11261 prime[1362]=11273 prime[1363]=11279 prime[1364]=11287 prime[1365]=11299 prime[1366]=11311 prime[1367]=11317 prime[1368]=11321 prime[1369]=11329 prime[1370]=11351 prime[1371]=11353 prime[1372]=11369 prime[1373]=11383 prime[1374]=11393 prime[1375]=11399 prime[1376]=11411 prime[1377]=11423 prime[1378]=11437 prime[1379]=11443 prime[1380]=11447 prime[1381]=11467 prime[1382]=11471 prime[1383]=11483 prime[1384]=11489 prime[1385]=11491 prime[1386]=11497 prime[1387]=11503 prime[1388]=11519 prime[1389]=11527 prime[1390]=11549 prime[1391]=11551 prime[1392]=11579 prime[1393]=11587 prime[1394]=11593 prime[1395]=11597 prime[1396]=11617 prime[1397]=11621 prime[1398]=11633 prime[1399]=11657 prime[1400]=11677 prime[1401]=11681 prime[1402]=11689 prime[1403]=11699 prime[1404]=11701 prime[1405]=11717 prime[1406]=11719 prime[1407]=11731 prime[1408]=11743 prime[1409]=11777 prime[1410]=11779 prime[1411]=11783 prime[1412]=11789 prime[1413]=11801 prime[1414]=11807 prime[1415]=11813 prime[1416]=11821 prime[1417]=11827 prime[1418]=11831 prime[1419]=11833 prime[1420]=11839 prime[1421]=11863 prime[1422]=11867 prime[1423]=11887 prime[1424]=11897 prime[1425]=11903 prime[1426]=11909 prime[1427]=11923 prime[1428]=11927 prime[1429]=11933 prime[1430]=11939 prime[1431]=11941 prime[1432]=11953 prime[1433]=11959 prime[1434]=11969 prime[1435]=11971 prime[1436]=11981 prime[1437]=11987 prime[1438]=12007 prime[1439]=12011 prime[1440]=12037 prime[1441]=12041 prime[1442]=12043 prime[1443]=12049 prime[1444]=12071 prime[1445]=12073 prime[1446]=12097 prime[1447]=12101 prime[1448]=12107 prime[1449]=12109 prime[1450]=12113 prime[1451]=12119 prime[1452]=12143 prime[1453]=12149 prime[1454]=12157 prime[1455]=12161 prime[1456]=12163 prime[1457]=12197 prime[1458]=12203 prime[1459]=12211 prime[1460]=12227 prime[1461]=12239 prime[1462]=12241 prime[1463]=12251 prime[1464]=12253 prime[1465]=12263 prime[1466]=12269 prime[1467]=12277 prime[1468]=12281 prime[1469]=12289 prime[1470]=12301 prime[1471]=12323 prime[1472]=12329 prime[1473]=12343 prime[1474]=12347 prime[1475]=12373 prime[1476]=12377 prime[1477]=12379 prime[1478]=12391 prime[1479]=12401 prime[1480]=12409 prime[1481]=12413 prime[1482]=12421 prime[1483]=12433 prime[1484]=12437 prime[1485]=12451 prime[1486]=12457 prime[1487]=12473 prime[1488]=12479 prime[1489]=12487 prime[1490]=12491 prime[1491]=12497 prime[1492]=12503 prime[1493]=12511 prime[1494]=12517 prime[1495]=12527 prime[1496]=12539 prime[1497]=12541 prime[1498]=12547 prime[1499]=12553 prime[1500]=12569 prime[1501]=12577 prime[1502]=12583 prime[1503]=12589 prime[1504]=12601 prime[1505]=12611 prime[1506]=12613 prime[1507]=12619 prime[1508]=12637 prime[1509]=12641 prime[1510]=12647 prime[1511]=12653 prime[1512]=12659 prime[1513]=12671 prime[1514]=12689 prime[1515]=12697 prime[1516]=12703 prime[1517]=12713 prime[1518]=12721 prime[1519]=12739 prime[1520]=12743 prime[1521]=12757 prime[1522]=12763 prime[1523]=12781 prime[1524]=12791 prime[1525]=12799 prime[1526]=12809 prime[1527]=12821 prime[1528]=12823 prime[1529]=12829 prime[1530]=12841 prime[1531]=12853 prime[1532]=12889 prime[1533]=12893 prime[1534]=12899 prime[1535]=12907 prime[1536]=12911 prime[1537]=12917 prime[1538]=12919 prime[1539]=12923 prime[1540]=12941 prime[1541]=12953 prime[1542]=12959 prime[1543]=12967 prime[1544]=12973 prime[1545]=12979 prime[1546]=12983 prime[1547]=13001 prime[1548]=13003 prime[1549]=13007 prime[1550]=13009 prime[1551]=13033 prime[1552]=13037 prime[1553]=13043 prime[1554]=13049 prime[1555]=13063 prime[1556]=13093 prime[1557]=13099 prime[1558]=13103 prime[1559]=13109 prime[1560]=13121 prime[1561]=13127 prime[1562]=13147 prime[1563]=13151 prime[1564]=13159 prime[1565]=13163 prime[1566]=13171 prime[1567]=13177 prime[1568]=13183 prime[1569]=13187 prime[1570]=13217 prime[1571]=13219 prime[1572]=13229 prime[1573]=13241 prime[1574]=13249 prime[1575]=13259 prime[1576]=13267 prime[1577]=13291 prime[1578]=13297 prime[1579]=13309 prime[1580]=13313 prime[1581]=13327 prime[1582]=13331 prime[1583]=13337 prime[1584]=13339 prime[1585]=13367 prime[1586]=13381 prime[1587]=13397 prime[1588]=13399 prime[1589]=13411 prime[1590]=13417 prime[1591]=13421 prime[1592]=13441 prime[1593]=13451 prime[1594]=13457 prime[1595]=13463 prime[1596]=13469 prime[1597]=13477 prime[1598]=13487 prime[1599]=13499 prime[1600]=13513 prime[1601]=13523 prime[1602]=13537 prime[1603]=13553 prime[1604]=13567 prime[1605]=13577 prime[1606]=13591 prime[1607]=13597 prime[1608]=13613 prime[1609]=13619 prime[1610]=13627 prime[1611]=13633 prime[1612]=13649 prime[1613]=13669 prime[1614]=13679 prime[1615]=13681 prime[1616]=13687 prime[1617]=13691 prime[1618]=13693 prime[1619]=13697 prime[1620]=13709 prime[1621]=13711 prime[1622]=13721 prime[1623]=13723 prime[1624]=13729 prime[1625]=13751 prime[1626]=13757 prime[1627]=13759 prime[1628]=13763 prime[1629]=13781 prime[1630]=13789 prime[1631]=13799 prime[1632]=13807 prime[1633]=13829 prime[1634]=13831 prime[1635]=13841 prime[1636]=13859 prime[1637]=13873 prime[1638]=13877 prime[1639]=13879 prime[1640]=13883 prime[1641]=13901 prime[1642]=13903 prime[1643]=13907 prime[1644]=13913 prime[1645]=13921 prime[1646]=13931 prime[1647]=13933 prime[1648]=13963 prime[1649]=13967 prime[1650]=13997 prime[1651]=13999 prime[1652]=14009 prime[1653]=14011 prime[1654]=14029 prime[1655]=14033 prime[1656]=14051 prime[1657]=14057 prime[1658]=14071 prime[1659]=14081 prime[1660]=14083 prime[1661]=14087 prime[1662]=14107 prime[1663]=14143 prime[1664]=14149 prime[1665]=14153 prime[1666]=14159 prime[1667]=14173 prime[1668]=14177 prime[1669]=14197 prime[1670]=14207 prime[1671]=14221 prime[1672]=14243 prime[1673]=14249 prime[1674]=14251 prime[1675]=14281 prime[1676]=14293 prime[1677]=14303 prime[1678]=14321 prime[1679]=14323 prime[1680]=14327 prime[1681]=14341 prime[1682]=14347 prime[1683]=14369 prime[1684]=14387 prime[1685]=14389 prime[1686]=14401 prime[1687]=14407 prime[1688]=14411 prime[1689]=14419 prime[1690]=14423 prime[1691]=14431 prime[1692]=14437 prime[1693]=14447 prime[1694]=14449 prime[1695]=14461 prime[1696]=14479 prime[1697]=14489 prime[1698]=14503 prime[1699]=14519 prime[1700]=14533 prime[1701]=14537 prime[1702]=14543 prime[1703]=14549 prime[1704]=14551 prime[1705]=14557 prime[1706]=14561 prime[1707]=14563 prime[1708]=14591 prime[1709]=14593 prime[1710]=14621 prime[1711]=14627 prime[1712]=14629 prime[1713]=14633 prime[1714]=14639 prime[1715]=14653 prime[1716]=14657 prime[1717]=14669 prime[1718]=14683 prime[1719]=14699 prime[1720]=14713 prime[1721]=14717 prime[1722]=14723 prime[1723]=14731 prime[1724]=14737 prime[1725]=14741 prime[1726]=14747 prime[1727]=14753 prime[1728]=14759 prime[1729]=14767 prime[1730]=14771 prime[1731]=14779 prime[1732]=14783 prime[1733]=14797 prime[1734]=14813 prime[1735]=14821 prime[1736]=14827 prime[1737]=14831 prime[1738]=14843 prime[1739]=14851 prime[1740]=14867 prime[1741]=14869 prime[1742]=14879 prime[1743]=14887 prime[1744]=14891 prime[1745]=14897 prime[1746]=14923 prime[1747]=14929 prime[1748]=14939 prime[1749]=14947 prime[1750]=14951 prime[1751]=14957 prime[1752]=14969 prime[1753]=14983 prime[1754]=15013 prime[1755]=15017 prime[1756]=15031 prime[1757]=15053 prime[1758]=15061 prime[1759]=15073 prime[1760]=15077 prime[1761]=15083 prime[1762]=15091 prime[1763]=15101 prime[1764]=15107 prime[1765]=15121 prime[1766]=15131 prime[1767]=15137 prime[1768]=15139 prime[1769]=15149 prime[1770]=15161 prime[1771]=15173 prime[1772]=15187 prime[1773]=15193 prime[1774]=15199 prime[1775]=15217 prime[1776]=15227 prime[1777]=15233 prime[1778]=15241 prime[1779]=15259 prime[1780]=15263 prime[1781]=15269 prime[1782]=15271 prime[1783]=15277 prime[1784]=15287 prime[1785]=15289 prime[1786]=15299 prime[1787]=15307 prime[1788]=15313 prime[1789]=15319 prime[1790]=15329 prime[1791]=15331 prime[1792]=15349 prime[1793]=15359 prime[1794]=15361 prime[1795]=15373 prime[1796]=15377 prime[1797]=15383 prime[1798]=15391 prime[1799]=15401 prime[1800]=15413 prime[1801]=15427 prime[1802]=15439 prime[1803]=15443 prime[1804]=15451 prime[1805]=15461 prime[1806]=15467 prime[1807]=15473 prime[1808]=15493 prime[1809]=15497 prime[1810]=15511 prime[1811]=15527 prime[1812]=15541 prime[1813]=15551 prime[1814]=15559 prime[1815]=15569 prime[1816]=15581 prime[1817]=15583 prime[1818]=15601 prime[1819]=15607 prime[1820]=15619 prime[1821]=15629 prime[1822]=15641 prime[1823]=15643 prime[1824]=15647 prime[1825]=15649 prime[1826]=15661 prime[1827]=15667 prime[1828]=15671 prime[1829]=15679 prime[1830]=15683 prime[1831]=15727 prime[1832]=15731 prime[1833]=15733 prime[1834]=15737 prime[1835]=15739 prime[1836]=15749 prime[1837]=15761 prime[1838]=15767 prime[1839]=15773 prime[1840]=15787 prime[1841]=15791 prime[1842]=15797 prime[1843]=15803 prime[1844]=15809 prime[1845]=15817 prime[1846]=15823 prime[1847]=15859 prime[1848]=15877 prime[1849]=15881 prime[1850]=15887 prime[1851]=15889 prime[1852]=15901 prime[1853]=15907 prime[1854]=15913 prime[1855]=15919 prime[1856]=15923 prime[1857]=15937 prime[1858]=15959 prime[1859]=15971 prime[1860]=15973 prime[1861]=15991 prime[1862]=16001 prime[1863]=16007 prime[1864]=16033 prime[1865]=16057 prime[1866]=16061 prime[1867]=16063 prime[1868]=16067 prime[1869]=16069 prime[1870]=16073 prime[1871]=16087 prime[1872]=16091 prime[1873]=16097 prime[1874]=16103 prime[1875]=16111 prime[1876]=16127 prime[1877]=16139 prime[1878]=16141 prime[1879]=16183 prime[1880]=16187 prime[1881]=16189 prime[1882]=16193 prime[1883]=16217 prime[1884]=16223 prime[1885]=16229 prime[1886]=16231 prime[1887]=16249 prime[1888]=16253 prime[1889]=16267 prime[1890]=16273 prime[1891]=16301 prime[1892]=16319 prime[1893]=16333 prime[1894]=16339 prime[1895]=16349 prime[1896]=16361 prime[1897]=16363 prime[1898]=16369 prime[1899]=16381 prime[1900]=16411 prime[1901]=16417 prime[1902]=16421 prime[1903]=16427 prime[1904]=16433 prime[1905]=16447 prime[1906]=16451 prime[1907]=16453 prime[1908]=16477 prime[1909]=16481 prime[1910]=16487 prime[1911]=16493 prime[1912]=16519 prime[1913]=16529 prime[1914]=16547 prime[1915]=16553 prime[1916]=16561 prime[1917]=16567 prime[1918]=16573 prime[1919]=16603 prime[1920]=16607 prime[1921]=16619 prime[1922]=16631 prime[1923]=16633 prime[1924]=16649 prime[1925]=16651 prime[1926]=16657 prime[1927]=16661 prime[1928]=16673 prime[1929]=16691 prime[1930]=16693 prime[1931]=16699 prime[1932]=16703 prime[1933]=16729 prime[1934]=16741 prime[1935]=16747 prime[1936]=16759 prime[1937]=16763 prime[1938]=16787 prime[1939]=16811 prime[1940]=16823 prime[1941]=16829 prime[1942]=16831 prime[1943]=16843 prime[1944]=16871 prime[1945]=16879 prime[1946]=16883 prime[1947]=16889 prime[1948]=16901 prime[1949]=16903 prime[1950]=16921 prime[1951]=16927 prime[1952]=16931 prime[1953]=16937 prime[1954]=16943 prime[1955]=16963 prime[1956]=16979 prime[1957]=16981 prime[1958]=16987 prime[1959]=16993 prime[1960]=17011 prime[1961]=17021 prime[1962]=17027 prime[1963]=17029 prime[1964]=17033 prime[1965]=17041 prime[1966]=17047 prime[1967]=17053 prime[1968]=17077 prime[1969]=17093 prime[1970]=17099 prime[1971]=17107 prime[1972]=17117 prime[1973]=17123 prime[1974]=17137 prime[1975]=17159 prime[1976]=17167 prime[1977]=17183 prime[1978]=17189 prime[1979]=17191 prime[1980]=17203 prime[1981]=17207 prime[1982]=17209 prime[1983]=17231 prime[1984]=17239 prime[1985]=17257 prime[1986]=17291 prime[1987]=17293 prime[1988]=17299 prime[1989]=17317 prime[1990]=17321 prime[1991]=17327 prime[1992]=17333 prime[1993]=17341 prime[1994]=17351 prime[1995]=17359 prime[1996]=17377 prime[1997]=17383 prime[1998]=17387 prime[1999]=17389 prime[2000]=17393 prime[2001]=17401 prime[2002]=17417 prime[2003]=17419 prime[2004]=17431 prime[2005]=17443 prime[2006]=17449 prime[2007]=17467 prime[2008]=17471 prime[2009]=17477 prime[2010]=17483 prime[2011]=17489 prime[2012]=17491 prime[2013]=17497 prime[2014]=17509 prime[2015]=17519 prime[2016]=17539 prime[2017]=17551 prime[2018]=17569 prime[2019]=17573 prime[2020]=17579 prime[2021]=17581 prime[2022]=17597 prime[2023]=17599 prime[2024]=17609 prime[2025]=17623 prime[2026]=17627 prime[2027]=17657 prime[2028]=17659 prime[2029]=17669 prime[2030]=17681 prime[2031]=17683 prime[2032]=17707 prime[2033]=17713 prime[2034]=17729 prime[2035]=17737 prime[2036]=17747 prime[2037]=17749 prime[2038]=17761 prime[2039]=17783 prime[2040]=17789 prime[2041]=17791 prime[2042]=17807 prime[2043]=17827 prime[2044]=17837 prime[2045]=17839 prime[2046]=17851 prime[2047]=17863 define perfect_power(n){ auto i,t,x,y /* Here 2^prime[2047] >=n > 1. * If n is a perfect power, returns p, where n = x^p, p minimal. * Otherwise returns zero. * See E. Bach and J. Sorenson, "Sieve algorithms for perfect power testing" * Algorithmica 9 (1993) 313-328. */ t=binary_log(n) i=0 while(prime[i]<=t){ x=mthroot(n,1,prime[i]) y=x^prime[i] if(y==n){ print n,"=",x,"^" return(prime[i]) }else{ i=i+1 } } return(0) }