#include<stdio.h>
#include<math.h>
FILE *f,*g;
int v[]={0,2,3,7,13,19,25,31,39,43,49,55,61,69,73,81,85,91,99,103,109,115,123,129,133,139,147,151,159,165,169,175,181,187,193,199,207,213,225,229,235,241,253,259,265,271,279,283,291,295,309,313,319,333,337,349,355,361,369,375,381,385,391,397,403,409,417,421,433,441,445,451,459,463,469,481,487,493,501,505,511,519,523,531,537,543,549,559,565,571,579,585,589,595,601,609,615,619,631,637,643,649,655,661,669,675,679,685,693,699,703,711,721,729,735,739,745,753,759,763,771,775,783,787,799,811,817,823,829,837,841,853,859,865,871,879,883,889,897,903,909,913,921,931,939,943,949,955,969,973,979,985,993,999,1005,1011,1015,1021,1033,1041,1051,1057,1063,1069,1075,1083,1089,1093,1099,1105,1111,1117,1125,1131,1137,1141,1153,1165,1173,1179,1183,1189,1195,1203,1209,1215,1219,1225,1231,1239,1245,1251,1257,1261,1279,1285,1291,1299,1303,1309,1317,1321,1329,1333,1345,1359,1363,1369,1375,1383,1387,1399,1407,1411,1425,1429,1435,1441,1449,1453,1461,1467,1473,1483,1489,1495,1501,1509,1513,1519,1525,1533,1537,1543,1551,1555,1561,1569,1573,1581,1585,1599,1603,1609,1615,1621,1629,1635,1639,1651,1657,1665,1669,1683,1695,1699,1711,1719,1723,1729,1735,1741,1749,1755,1761,1767,1779,1785,1789,1795,1803,1813,1819,1825,1833,1837,1849,1863,1867,1873,1879,1891,1897,1903,1909,1915,1923,1929,1933,1945,1951,1963,1971,1975,1981,1989,1995,1999,2005,2013,2019,2029,2041,2049,2055,2061,2065,2071,2083,2089,2097,2101,2113,2131,2139,2143,2155,2161,2169,2175,2181,2185,2197,2205,2209,2215,2223,2229,2233,2239,2245,2253,2269,2275,2283,2287,2293,2299,2307,2311,2323,2331,2335,2341,2349,2353,2359,2373,2379,2383,2391,2395,2401,2409,2413,2419,2425,2439,2443,2449,2455,2461,2469,2475,2479,2493,2497,2505,2517,2523,2533,2541,2545,2551,2559,2565,2581,2593,2601,2607,2611,2619,2623,2629,2635,2649,2659,2665,2671,2679,2685,2689,2695,2701,2707,2713,2721,2731,2737,2743,2749,2755,2763,2769,2773,2779,2787,2791,2799,2803,2811,2815,2821,2829,2835,2839,2845,2853,2859,2863,2881,2887,2895,2899,2905,2911,2919,2923,2929,2937,2941,2955,2959,2965,2971,2997,3001,3013,3021,3025,3037,3043,3049,3063,3067,3073,3081,3085,3091,3105,3111,3121,3129,3139,3151,3165,3169,3183,3189,3193,3205,3211,3219,3223,3231,3237,3241,3249,3253,3259,3267,3273,3279,3295,3301,3309,3315,3321,3325,3331,3339,3345,3349,3361,3367,3373,3379,3387,3391,3405,3409,3415,3423,3429,3435,3451,3457,3463,3469,3483,3489,3493,3501,3507,3513,3519,3529,3535,3541,3547,3553,3559,3573,3583,3589,3595,3609,3613,3619,3625,3633,3637,3643,3651,3661,3667,3673,3679,3685,3693,3699,3703,3711,3715,3721,3729,3735,3739,3751,3757,3763,3769,3781,3787,3793,3799,3805,3819,3823,3835,3843,3847,3853,3861,3865,3879,3883,3891,3903,3909,3913,3919,3925,3931,3945,3949,3955,3961,3969,3975,3979,3987,3991,4003,4009,4015,4021,4029,4039,4047,4051,4059,4065,4075,4081,4093,4101,4105,4113,4119,4129,4135,4141,4155,4159,4171,4179,4183,4189,4197,4203,4213,4219,4231,4243,4255,4261,4269,4273,4281,4285,4291,4299,4317,4323,4329,4339,4351,4359,4365,4371,4375,4387,4393,4399,4407,4411,4423,4437,4443,4449,4453,4459,4465,4473,4479,4483,4491,4495,4509,4515,4519,4525,4533,4537,4549,4555,4561,4569,4575,4585,4593,4597,4605,4611,4623,4635,4639,4645,4651,4659,4663,4675,4681,4687,4693,4701,4705,4711,4719,4723,4729,4735,4743,4749,4753,4759,4767,4779,4785,4789,4795,4801,4815,4819,4831,4837,4845,4849,4855,4863,4873,4879,4887,4891,4899,4905,4911,4915,4921,4933,4939,4945,4953,4957,4969,4975,4983,4987,4995,5001,5005,5011,5019,5023,5029,5041,5047,5053,5061,5067,5071,5079,5083,5089,5097,5101,5109,5115,5121,5131,5139,5143,5149,5155,5169,5173,5181,5191,5197,5209,5221,5229,5233,5239,5247,5253,5263,5271,5275,5281,5289,5295,5299,5305,5311,5325,5335,5349,5353,5361,5367,5373,5383,5389,5395,5401,5409,5415,5419,5433,5437,5443,5451,5457,5473,5479,5485,5491,5499,5503,5509,5515,5521,5529,5533,5541,5547,5559,5563,5571,5575,5583,5593,5601,5611,5617,5625,5629,5641,5647,5653,5659,5671,5685,5689,5695,5703,5713,5719,5725,5733,5739,5743,5751,5757,5775,5781,5785,5793,5803,5809,5815,5823,5829,5841,5845,5851,5857,5863,5869,5881,5895,5899,5905,5913,5925,5929,5937,5941,5953,5961,5965,5971,5983,5989,6003,6007,6013,6019,6031,6039,6045,6049,6055,6067,6075,6081,6087,6091,6103,6111,6115,6121,6129,6133,6145,6153,6159,6165,6175,6181,6187,6195,6199,6205,6213,6219,6223,6231,6241,6247,6259,6265,6271,6279,6289,6297,6301,6313,6319,6325,6331,6339,6343,6349,6355,6361,6369,6373,6381,6387,6391,6399,6403,6415,6423,6429,6439,6445,6451,6459,6465,6469,6475,6483,6487,6493,6501,6507,6513,6523,6531,6537,6549,6553,6559,6565,6571,6579,6583,6591,6597,6601,6609,6615,6621,6625,6637,6655,6661,6669,6675,6679,6685,6691,6703,6711,6721,6733,6739,6745,6759,6763,6769,6781,6789,6793,6805,6819,6825,6829,6835,6843,6849,6859,6865,6871,6885,6889,6901,6907,6913,6919,6933,6945,6949,6961,6969,6973,6979,6985,6993,6999,7003,7015,7021,7029,7033,7041,7045,7053,7059,7063,7069,7081,7095,7105,7111,7117,7123,7129,7137,7153,7161,7167,7171,7179,7185,7189,7195,7209,7213,7221,7231,7237,7245,7249,7255,7263,7281,7285,7291,7297,7309,7323,7329,7333,7341,7351,7357,7371,7381,7389,7395,7405,7413,7419,7435,7449,7453,7459,7465,7479,7483,7489,7495,7501,7509,7515,7519,7525,7531,7539,7543,7549,7557,7561,7573,7579,7585,7591,7599,7603,7609,7615,7623,7629,7635,7641,7645,7651,7657,7663,7671,7675,7683,7689,7693,7701,7705,7713,7719,7725,7729,7743,7747,7755,7759,7767,7771,7791,7795,7801,7809,7819,7825,7831,7837,7843,7851,7855,7869,7875,7879,7885,7897,7903,7909,7917,7921,7929,7935,7939,7951,7965,7981,7987,7995,7999,8007,8011,8019,8025,8035,8041,8053,8061,8065,8071,8079,8083,8089,8095,8103,8109,8113,8119,8125,8133,8137,8145,8149,8163,8169,8173,8181,8187,8193,8211,8221,8233,8239,8245,8253,8259,8263,8271,8275,8289,8293,8299,8313,8317,8323,8329,8337,8349,8355,8365,8371,8379,8385,8389,8401,8407,8415,8421,8425,8431,8443,8449,8455,8461,8467,8485,8499,8503,8511,8515,8523,8529,8539,8545,8553,8565,8575,8581,8593,8599,8607,8611,8623,8629,8635,8641,8649,8653,8665,8671,8679,8683,8691,8695,8701,8709,8715,8719,8733,8737,8743,8749,8755,8763,8767,8779,8785,8793,8797,8805,8809,8821,8833,8839,8845,8851,8859,8863,8869,8883,8887,8895,8901,8905,8917,8925,8929,8935,8943,8949,8953,8965,8971,8979,8991,9001,9007,9013,9019,9031,9043,9051,9057,9061,9069,9093,9099,9105,9111,9117,9129,9135,9139,9145,9153,9157,9163,9171,9175,9181,9189,9195,9199,9205,9211,9223,9229,9237,9241,9259,9265,9279,9283,9289,9295,9301,9307,9313,9321,9325,9339,9343,9351,9357,9373,9379,9387,9393,9399,9405,9411,9415,9421,9429,9433,9439,9447,9463,9469,9475,9481,9489,9493,9499,9507,9511,9523,9535,9541,9549,9553,9561,9567,9573,9589,9601,9615,9619,9625,9631,9639,9645,9649,9657,9663,9675,9679,9691,9699,9717,9721,9729,9733,9741,9745,9751,9759,9769,9783,9789,9793,9799,9805,9811,9819,9831,9835,9841,9853,9859,9867,9873,9885,9889,9897,9903,9909,9915,9919,9925,9931,9937,9943,9951,9955,9967,9975,9979,9985,10009,10017,10023,10035,10039,10057,10063,10069,10081,10087,10093,10099,10105,10111,10125,10135,10141,10153,10161,10165,10171,10179,10183,10191,10195,10203,10209,10213,10221,10225,10239,10245,10249,10255,10261,10267,10273,10291,10303,10309,10315,10321,10329,10333,10339,10345,10351,10359,10371,10381,10393,10399,10407,10413,10419,10423,10429,10435,10443,10455,10459,10465,10479,10483,10489,10497,10501,10513,10521,10531,10539,10543,10557,10561,10569,10581,10591,10599,10603,10609,10615,10629,10633,10639,10645,10653,10659,10665,10669,10683,10687,10693,10707,10711,10725,10731,10735,10741,10749,10755,10767,10773,10783,10791,10801,10809,10815,10819,10825,10833,10839,10843,10849,10855,10861,10869,10875,10885,10891,10897,10903,10911,10923,10939,10951,10959,10963,10969,10975,10981,10989,10993,11001,11005,11017,11029,11037,11049,11059,11067,11071,11085,11089,11095,11101,11107,11115,11119,11133,11145,11149,11161,11173,11179,11185,11191,11199,11205,11211,11215,11235,11241,11245,11253,11257,11263,11271,11275,11281,11289,11295,11301,11305,11313,11319,11323,11331,11337,11343,11353,11359,11367,11371,11385,11395,11401,1140711413,11425,11431,11439,11443,11449,11457,11469,11473,11479,11485,11491,11499,11505,11509,11521,11529,11541,11547,11551,11571,11575,11581,11589,11593,11599,11613,11619,11623,11631,11635,11659,11667,11673,11679,11683,11691,11697,11701,11709,11719,11731,11737,11745,11749,11757,11773,11779,11785,11791,11799,11803,11809,11815,11821,11829,11833,11841,11851,11857,11865,11869,11887,11899,11905,11911,11919,11925,11929,11935,11941,11947,11955,11959,11967,11971,11983,11989,11995,12003,12009,12013,12033,12037,12043,12051,12055,12069,12073,12081,12087,12093,12099,12103,12109,12115,12121,12135,12145,12151,12159,12163,12169,12187,12195,12199,12205,12213,12225,12229,12237,12241,12249,12253,12265,12271,12279,12283,12291,12297,12303,12321,12325,12331,12337,12345,12349,12355,12361,12367,12375,12379,12387,12393,12403,12411,12415,12421,12435,12439,12445,12451,12459,12463,12475,12481,12489,12493,12499,12505,12513,12517,12529,12541,12549,12555,12571,12579,12583,12589,12603,12607,12613,12621,12633,12639,12643,12649,12655,12661,12669,12673,12691,12697,12705,12709,12715,12723,12733,12741,12745,12753,12759,12765,12769,12783,12787,12793,12799,12811,12823,12829,12841,12849,12855,12871,12879,12883,12891,12895,12901,12909,12913,12919,12925,12939,12943,12949,12955,12961,12969,12975,12981,12985,12993,12999,13003,13009,13021,13033,13039,13045,13051,13059,13063,13075,13087,13095,13101,13105,13111,13123,13129,13143,13149,13153,13159,13165,13173,13179,13185,13189,13195,13201,13209,13213,13219,13231,13237,13243,13251,13255,13261,13269,13273,13285,13291,13299,13305,13311,13315,13329,13333,13339,13345,13369,13383,13387,13395,13399,13413,13417,13423,13437,13443,13453,13459,13465,13471,13479,13489,13497,13501,13515,13521,13525,13531,13539,13545,13551,13555,13563,13569,13573,13579,13591,13597,13609,13615,13621,13629,13635,13641,13647,13651,13669,13675,13681,13689,13693,13699,13707,13711,13723,13731,13737,13741,13749,13753,13759,13765,13773,13779,13783,13791,13801,13809,13831,13837,13843,13851,13861,13875,13879,13885,13893,13903,13909,13915,13923,13933,13941,13947,13959,13963,13969,13975,13987,13999,14007,14011,14019,14025,14031,14035,14049,14053,14059,14067,14073,14083,14089,14097,14101,14109,14115,14139,14143,14151,14155,14161,14167,14173,14179,14187,14193,14199,14209,14217,14223,14229,14241,14245,14251,14257,14265,14269,14283,14287,14295,14305,14313,14323,14329,14343,14349,14353,14361,14371,14379,14389,14395,14403,14409,14413,14421,14425,14431,14439,14449,14455,14463,14473,14481,14487,14491,14505,14509,14517,14521,14535,14539,14545,14551,14559,14563,14571,14587,14593,14599,14619,14623,14629,14635,14641,14655,14659,14671,14683,14697,14701,14715,14719,14725,14733,14739,14743,14749,14755,14761,14767,14773,14781,14785,14799,14805,14811,14815,14823,14829,14833,14839,14845,14853,14859,14865,14869,14881,14889,14893,14899,14911,14925,14931,14941,14949,14953,14959,14971,14979,14983,14997,15015,15019,15033,15039,15049,15055,15063,15075,15079,15085,15091,15097,15103,15109,15117,15123,15133,15139,15151,15159,15163,15175,15189,15193,15201,15207,15211,15219,15229,15235,15243,15261,15265,15271,15279,15289,15295,15301,15307,15315,15319,15331,15343,15351,15357,15361,15369,15375,15379,15385,15393,15397,15403,15415,15421,15429,15441,15445,15453,15463,15469,15475,15481,15489,15495,15499,15505,15513,15517,15529,15541,15547,15553,15559,15565,15571,15583,15597,15603,15609,15613,15621,15625,15631,15643,15649,15655,15663,15669,15673,15681,15685,15691,15699,15705,15711,15729,15733,15739,15751,15763,15769,15775,15789,15793,15799,15805,15811,15817,15825,15831,15835,15855,15859,15865,15873,15879,15883,15889,15895,15903,15907,15915,15919,15925,15931,15937,15945,15949,15957,15961,15973,15993,15999,16003,16009,16015,16035,16047,16051,16059,16063,16069,16075,16087,16093,16099,16105,16113,16119,16125,16129,16141,16147,16155,16183,16189,16195,16201,16219,16225,16231,16245,16251,16255,16269,16273,16287,16293,16303,16309,16321,16329,16335,16341,16345,16351,16357,16363,16371,16383,16393,16413,16419,16423,16429,16435,16441,16449,16453,16465,16479,16483,16489,16495,16503,16509,16521,16531,16537,16545,16549,16555,16563,16567,16575,16579,16593,16597,16605,16609,16615,16621,16633,16639,16647,16651,16659,16663,16671,16675,16693,16701,16705,16713,16717,16723,16731,16735,16743,16749,16755,16761,16765,16783,16789,16797,16801,16813,16819,16825,16831,16839,16843,16849,16857,16861,16869,16873,16881,16885,16891,16903,16911,16923,16929,16933,16939,16945,16951,16965,16971,16981,16989,16995,17001,17013,17017,17023,17029,17035,17041,17049,17053,17059,17067,17079,17085,17091,17095,17101,17109,17119,17125,17139,17151,17155,17161,17167,17181,17185,17191,17199,17205,17209,17221,17233,17239,17247,17251,17259,17275,17281,17289,17293,17301,17307,17319,17323,17329,17335,17343,17353,17361,17365,17371,17379,17385,17389,17395,17401,17413,17419,17433,17443,17451,17457,17469,17473,17479,17485,17491,17497,17505,17511,17515,17521,17529,17533,17541,17545,17553,17557,17569,17575,17581,17587,17599,17605,17611,17619,17623,17629,17637,17659,17665,17671,17679,17683,17689,17697,17709,17715,17725,17731,17739,17743,17749,17763,17779,17785,17791,17809,17815,17823,17829,17835,17839,17853,17857,17865,17871,17883,17893,17899,17905,17911,17923,17931,17935,17941,17949,17959,17967,17973,17979,17983,17989,18001,18009,18015,18025,18037,18043,18049,18061,18079,18087,18091,18099,18115,18121,18129,18133,18145,18151,18157,18165,18169,18183,18193,18201,18213,18219,18225,18231,18235,18249,18253,18259,18271,18285,18289,18295,18303,18309,18313,18331,18339,18343,18351,18355,18369,18373,18381,18387,18393,18399,18403,18409,18415,18421,18429,18435,18441,18445,18453,18457,18463,18481,18487,18495,18505,18511,18519,18523,18529,18541,18547,18555,18561,18585,18589,18595,18609,18613,18619,18625,18637,18651,18663,18667,18673,18681,18693,18703,18711,18715,18721,18733,18739,18745,18751,18759,18765,18771,18775,18781,18789,18795,18799,18805,18829,18835,18841,18849,18855,18861,18871,18883,18897,18901,18913,18919,18925,18933,18939,18949,18961,18975,18981,18987,18999,19003,19011,19015,19023,19029,19033,19039,19053,19065,19071,19075,19081,19089,19093,19101,19107,19111,19123,19131,19141,19149,19155,19159,19165,19183,19195,19209,19213,19219,19233,19239,19251,19257,19261,19269,19275,19279,19285,19291,19299,19303,19311,19317,19321,19335,19341,19351,19365,19375,19381,19387,19393,19405,19419,19423,19429,19435,19443,19447,19453,19459,19465,19471,19479,19485,19491,19503,19509,19519,19531,19537,19543,19549,19555,19561,19569,19573,19579,19585,19599,19605,19611,19615,19633,19641,19647,19659,19663,19669,19683,19689,19695,19699,19711,19717,19725,19729,19737,19741,19753,19761,19765,19771,19779,19795,19803,19809,19813,19821,19831,19837,19843,19849,19855,19863,19869,19887,19891,19899,19909,19915,19921,19929,19939,19947,19951,19963,19975,19981,19993,19999,20007,20013,20019,20023,20031,20037,20041,20049,20053,20065,20073,20079,20089,20097,20103,20109,20115,20119,20125,20131,20137,20143,20149,20163,20173,20179,20185,20203,20221,20229,20233,20241,20247,20251,20259,20263,20271,20283,20287,20299,20305,20319,20325,20329,20335,20343,20349,20355,20359,20367,20371,20391,20395,20401,20409,20413,20419,20433,20439,20443,20457,20461,20469,20473,20479,20485,20497,20509,20521,20535,20545,20551,20557,20563,20569,20583,20595,20601,20611,20619,20623,20629,20635,20641,20649,20665,20683,20691,20695,20703,20709,20719,20733,20739,20745,20749,20755,20761,20767,20773,20779,20787,20791,20805,20809,20823,20829,20833,20839,20851,20859,20863,20871,20875,20881,20887,20895,20899,20905,20913,20923,20931,20941,20949,20955,20961,20965,20979,20983,21003,21007,21013,21019,21025,21031,21045,21055,21061,21069,21081,21085,21091,21103,21109,21123,21139,21145,21151,21159,21165,21171,21181,21189,21193,21207,21211,21223,21229,21235,21241,21249,21253,21259,21267,21271,21279,21285,21297,21313,21319,21325,21333,21343,21349,21355,21363,21369,21379,21385,21393,21399,21403,21409,21417,21421,21435,21441,21447,21469,21481,21487,21493,21501,21505,21511,21519,21523,21531,21549,21553,21559,21565,21571,21579,21585,21589,21601,21613,21619,21633,21637,21645,21649,21655,21661,21669,21675,21685,21703,21711,21715,21721,21729,21739,21747,21753,21759,21769,21775,21781,21787,21799,21805,21813,21817,21823,21831,21841,21853,21859,21865,21873,21879,21883,21895,21913,21921,21925,21931,21939,21943,21951,21955,21963,21969,21973,21979,21987,21993,21999,22005,22009,22015,22021,22029,22033,22039,22047,22051,22065,22069,22075,22081,22093,22107,22111,22119,22123,22131,22135,22149,22155,22159,22165,22173,22179,22183,22189,22195,22201,22207,22221,22231,22237,22243,22249,22257,22261,22273,22279,22285,22293,22299,22303,22309,22317,22329,22333,22341,22345,22351,22363,22369,22383,22393,22399,22407,22411,22419,22425,22429,22435,22443,22447,22455,22461,22467,22471,22483,22503,22509,22513,22525,22533,22537,22543,22551,22561,22567,22573,22579,22585,22599,22603,22611,22615,22621,22639,22645,22653,22665,22671,22681,22693,22699,22711,22719,22723,22729,22735,22741,22753,22761,22767,22771,22779,22785,22789,22795,22809,22813,22819,22831,22837,22845,22855,22861,22873,22879,22893,22903,22909,22917,22923,22929,22933,22939,22945,22953,22957,22963,22975,22993,23005,23013,23017,23023,23029,23041,23055,23059,23065,23073,23079,23083,23089,23101,23107,23115,23119,23133,23139,23145,23149,23161,23169,23175,23185,23191,23199,23203,23209,23217,23223,23229,23241,23247,23251,23269,23281,23287,23293,23299,23313,23323,23329,23335,23341,23359,23367,23371,23395,23401,23409,23419,23433,23439,23449,23455,23461,23475,23479,23497,23503,23509,23517,23533,23539,23551,23559,23563,23569,23583,23595,23601,23605,23611,23625,23629,23635,23643,23653,23659,23665,23671,23679,23685,23689,23703,23715,23719,23743,23749,23755,23763,23769,23775,23791,23799,23803,23811,23815,23821,23829,23833,23839,23845,23859,23863,23871,23875,23881,23889,23895,23899,23911,23917,23925,23931,23937,23941,23955,23959,23967,23971,23979,23983,23995,24003,24009,24021,24025,24031,24045,24051,24055,24063,24067,24073,24079,24085,24093,24099,24105,24109,24115,24123,24129,24135,24139,24153,24163,24171,24181,24193,24199,24205,24217,24223,24231,24235,24241,24249,24253,24259,24279,24283,24289,24307,24315,24319,24331,24339,24345,24349,24357,24361,24373,24381,24385,24393,24405,24409,24415,24421,24433,24441,24445,24465,24471,24475,24483,24489,24501,24511,24517,24525,24529,24535,24547,24553,24561,24571,24591,24595,24601,24609,24613,24625,24633,24639,24651,24655,24661,24669,24673,24679,24685,24693,24699,24711,24717,24723,24735,24751,24757,24763,24769,24783,24795,24801,24805,24811,24823,24837,24843,24849,24853,24861,24865,24879,24885,24889,24903,24909,24919,24925,24931,24939,24945,24955,24967,24973,24979,24991,24997,25003,25009,25015,25021,25029,25033,25039,25045,25051,25059,25065,25075,25089,25093,25099,25107,25113,25119,25123,25129,25135,25149,25155,25165,25171,25179,25185,25191,25197,25201,25221,25231,25239,25245,25249,25255,25263,25269,25273,25281,25297,25303,25309,25323,25341,25345,25351,25359,25369,25375,25383,25387,25393,25401,25407,25411,25425,25429,25435,25441,25449,25455,25459,25465,25471,25483,25491,25497,25509,25513,25525,25533,25537,25543,25551,25563,25567,25575,25579,25585,25591,25597,25603,25611,25623,25635,25641,25645,25653,25659,25663,25669,25675,25681,25689,25695,25705,25711,25719,25725,25731,25735,25743,25749,25761,25765,25773,25779,25791,25795,25801,25809,25815,25819,25831,25837,25843,25849,25857,25863,25869,25875,25891,25897,25903,25915,25921,25929,25933,25939,25945,25953,25959,25969,25983,25999,26005,26019,26023,26029,26037,26043,26055,26059,26065,26079,26083,26095,26101,26109,26113,26121,26137,26143,26149,26155,26163,26169,26173,26179,26185,26191,26205,26211,26221,26229,26235,26239,26251,26263,26269,26281,26295,26299,26305,26311,26319,26323,26331,26335,26341,26349,26359,26367,26373,26389,26395,26401,26409,26419,26425,26433,26439,26449,26461,26467,26475,26481,26485,26491,26499,26503,26515,26523,26529,26541,26547,26559,26563,26571,26575,26589,26593,26599,26605,26617,26629,26635,26641,26649,26653,26661,26667,26671,26683,26689,26695,26701,26709,26713,26719,26725,26731,26737,26745,26751,26757,26761,26775,26779,26785,26799,26803,26809,26815,26823,26835,26841,26845,26851,26859,26863,26869,26881,26893,26901,26905,26911,26919,26923,26929,26935,26943,26949,26953,26961,26965,26979,26983,26989,26995,27009,27013,27019,27033,27037,27045,27051,27061,27067,27075,27079,27087,27093,27105,27109,27121,27129,27139,27145,27151,27157,27163,27171,27175,27181,27193,27199,27205,27213,27219,27223,27241,27247,27255,27259,27273,27279,27283,27291,27301,27321,27325,27331,27339,27357,27363,27369,27387,27399,27403,27409,27415,27423,27429,27433,27439,27451,27459,27465,27475,27481,27489,27493,27501,27507,27511,27525,27529,27535,27541,27553,27583,27591,27595,27613,27619,27625,27633,27637,27643,27649,27655,27661,27675,27681,27691,27699,27703,27733,27739,27745,27751,27759,27765,27769,27775,27781,27787,27793,27801,27805,27811,27819,27825,27829,27843,27847,27853,27867,27873,27885,27889,27895,27901,27907,27919,27931,27943,27949,27955,27963,27969,27975,27979,27985,27993,27999,28003,28011,28021,28029,28033,28041,28045,28053,28059,28071,28075,28083,28089,28099,28105,28111,28117,28125,28129,28143,28153,28159,28165,28183,28195,28201,28213,28221,28231,28257,28263,28269,28273,28279,28285,28291,28299,28309,28321,28333,28341,28347,28351,28363,28371,28383,28389,28395,28405,28411,28417,28423,28431,28435,28441,28449,28453,28461,28465,28473,28479,28495,28501,28507,28515,28519,28531,28539,28543,28549,28557,28561,28573,28579,28587,28593,28599,28603,28609,28621,28629,28633,28645,28651,28659,28663,28671,28675,28687,28699,28705,28713,28725,28729,28741,28747,28753,28761,28773,28783,28789,28795,28803,28809,28813,28819,28831,28839,28845,28851,28861,28869,28873,28879,28893,28897,28903,28909,28915,28923,28929,28935,28951,28957,28963,28971,28981,28993,29001,29007,29011,29019,29023,29029,29035,29043,29055,29061,29065,29071,29079,29103,29107,29119,29125,29131,29137,29149,29155,29169,29175,29179,29191,29197,29203,29209,29215,29223,29229,29233,29245,29253,29259,29263,29271,29289,29295,29299,29305,29313,29329,29335,29341,29349,29355,29365,29373,29379,29385,29389,29397,29401,29413,29425,29431,29439,29443,29449,29455,29461,29469,29475,29481,29485,29491,29503,29511,29515,29523,29529,29533,29539,29553,29559,29569,29575,29583,29589,29593,29601,29613,29617,29625,29631,29635,29641,29649,29665,29671,29679,29683,29691,29697,29701,29719,29725,29739,29743,29751,29755,29761,29781,29791,29799,29803,29809,29821,29833,29839,29853,29865,29869,29875,29881,29895,29901,29905,29911,29919,29923,29929,29935,29943,29949,29961,29985,29989,30013,30021,30031,30049,30055,30061,30069,30073,30085,30091,30099,30105,30111,30115,30121,30129,30133,30139,30147,30153,30159,30163,30169,30183,30187,30199,30205,30211,30217,30225,30237,30243,30255,30259,30267,30271,30285,30295,30309,30313,30321,30325,30339,30343,30349,30355,30367,30373,30379,30391,30397,30405,30411,30423,30429,30433,30439,30447,30451,30463,30469,30493,30499,30507,30511,30519,30523,30531,30541,30549,30553,30559,30567,30579,30583,30595,30601,30619,30633,30639,30645,30651,30657,30663,30673,30679,30691,30699,30705,30709,30715,30729,30733,30741,30751,30757,30765,30769,30775,30783,30789,30793,30805,30811,30817,30831,30841,30853,30861,30867,30871,30883,30889,30895,30901,30913,30931,30939,30943,30951,30961,30969,30973,30979,30985,30993,31009,31015,31021,31035,31039,31045,31053,31057,31065,31071,31081,31087,31093,31099,31107,31113,31123,31129,31135,31141,31147,31153,31161,31165,31171,31179,31183,31191,31195,31203,31209,31213,31221,31225,31233,31239,31249,31255,31261,31269,31273,31279,31287,31291,31303,31309,31317,31321,31329,31335,31339,31347,31353,31359,31363,31381,31387,31393,31399,31413,31419,31429,31437,31441,31455,31459,31471,31479,31483,31491,31497,31513,31519,31525,31531,31543,31549,31557,31569,31575,31581,31585,31603,31609,31617,31629,31633,31639,31645,31651,31659,31665,31669,31681,31687,31695,31701,31711,31723,31729,31743,31749,31753,31765,31771,31791,31795,31801,31809,31815,31819,31825,31837,31849,31861,31869,31875,31879,31885,31893,31897,31909,31921,31933,31947,31953,31959,31965,31975,31983,31987,31993,32001,32005,32011,32019,32029,32043,32053,32059,32065,32071,32079,32085,32089,32095,32101,32107,32113,32119,32137,32143,32161,32173,32185,32191,32199,32205,32215,32235,32239,32247,32253,32259,32263,32275,32289,32299,32305,32311,32319,32323,32329,32337,32343,32355,32361,32365,32371,32379,32383,32403,32407,32413,32421,32425,32431,32443,32449,32457,32469,32479,32485,32491,32497,32505,32509,32523,32529,32533,32539,32563,32569,32575,32581,32589,32595,32599,32605,32611,32623,32635,32641,32647,32655,32659,32665,32679,32689,32695,32703,32709,32715,32719,32731,32737,32743,32751,32757,32773,32781,32785,32791,32799,32803,32817,32821,32829,32833,32841,32845,32851,32865,32871,32883,32887,32899,32907,32911,32919,32935,32941,32949,32959,32971,32985,32989,32995,33001,33015,33025,33031,33037,33045,33051,33055,33073,33085,33093,33097,33103,33109,33115,33121,33129,33135,33151,33159,33163,33171,33181,33193,33199,33205,33211,33219,33225,33229,33249,33255,33267,33279,33283,33289,33297,33303,33313,33319,33325,33331};
int s,nd,n,t,i,j,d[100],e[100];
long long int nr;
int dle(int bz,int ex)
{
int r;
if(ex==1)
return bz%9973;
if(ex==0)
return 1;
r=dle(bz,ex/2)%9973;
r=(r*r)%9973;
return (9973+dle(bz,ex%2)*r)%9973;
}
int invers (int k)
{
int w=1;
while(w*k%9973!=1)
w++;
return w;
}
int fractie(int i)
{
int q,inv;
q=dle(d[i],e[i]+1);
inv=invers(d[i]-1);
return (9973+((9973+(9973+q-1))%9973)*inv)%9973;
}
int main() {
f=fopen("ssnd.in","r");
fscanf(f,"%d",&t);
g=fopen("ssnd.out","w");
for(i=1;i<=t;i++)
{
n=0;
nd=1;
s=1;
fscanf(f,"%lld",&nr);
j=1;
while(nr>1)
{
if(v[j]>sqrt(nr))
{
n++;
d[n]=nr;
e[n]=1;
nr=1;
}
if(nr%v[j]==0)
{
n++;
e[n]=0;
d[n]=v[j];
while(nr%v[j]==0)
{
e[n]++;
nr/=v[j];
}
}
}
for(i=1;i<=n;i++)
{
nd*=e[n]+1;
if(d[i]%9973==1)
s*=(e[i]+1);
else
s*=fractie(i);
s=s%9973;
}
fprintf(g,"%d %d\n",nd,s);
}
fclose(f);
fclose(g);
return 0;
}
Tanase Theodor iamdoru