/* 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)
}