P18579 [HackerEarth] All of us have read about factorials and Fibonacci numbers when we started studying algorithms. Today, we will be dealing with the factorials. They are very mystical in the sense that th
普及
题目描述

All of us have read about factorials and Fibonacci numbers when we started studying algorithms. Today, we will be dealing with the factorials. They are very mystical in the sense that they grow extremely fast. Fortunately, we can study their divisibility properties quite easily.

In the world of factorials we have a function f(N,A) which is the highest exponent of A dividing the factorial of N. Here, N is a nonnegative integer and A is a positive integer greater than 1. For example, f(5,2) = 3 as 2^3 divides 5! = 120 but 2^4 doesn't divide. Also, f(9,3) = 4 because 3^4 divides 9! but no other higher power of 3 divides it.

We are interested in investigating the function f(N,A) at a greater depth. For a given A, we want to know if there exists an N such that f(N,A) is between L and R, where L and R are the lower and upper bounds i.e., we want to know if there exists an integer N ≥ 0 such that L ≤ f(N,A) ≤ R. If there exists at least one such N, then your job is to output the largest valid candidate for N. Otherwise, output -1.

Input:

The first line of each test file contains a single integer T denoting the number of test cases.
T lines follow each containing 3 space separated integers A, L and R.

Output:

Output T lines each containing a single integer which is the largest N such that L ≤ f(N,A) ≤ R. In case such an N doesn't exist, then output "-1"(without quotes).

Constraints:

1 ≤ T ≤ 1000
2 ≤ A ≤ 100000000(10^8)
0 ≤ L ≤ R ≤ 10000000000(10^10)

It is assured that the result fits in a 64-bit signed integer.

SAMPLE INPUT
2
2 1 1
2 1 2
2 2 2

SAMPLE OUTPUT
3
3
-1

Explanation

In the first case, the result is 3 because f(N,2) = 1 is valid for N = 2, 3. So 3 is the answer.
In the second case, the result is 3 because 1 ≤ f(N,2) ≤ 2 for N = 2, 3. Note that f(4,2) = 3 so 4 doesn't satisfy the constraints.

输入格式

见题面

输出格式

见题面

样例输入
1000 2 1 1 2 1 2 2 1 3 2 2 2 3 1 1 3 3 3 4 1 2 4 2 3 6 2 2 6 2 3 2 0 0 2 0 100000000 12 10000 100000000 12 10000000 10000001 15 28 28 15 29 30 15 28 31 7 0 0 11 0 0 103 0 0 96854213 96854214 96854214 72974677 72974678 72974678 88433753 88433754 88433754 79499957 79499958 79499958 83793329 83793330 83793330 84426737 84426738 84426738 96791117 96791118 96791118 88512271 88512272 88512272 88294721 88294722 88294722 80974363 80974364 80974364 76395227 76395228 76395228 81462991 81462992 81462992 78816203 78816204 78816204 86370191 86370192 86370192 99255007 99255008 99255008 75263179 75263180 75263180 69213059 69213060 69213060 91149887 91149888 91149888 79765643 79765644 79765644 83391281 83391282 83391282 80713781 80713782 80713782 91455149 91455150 91455150 74094883 74094884 74094884 94595057 94595058 94595058 90087089 90087090 90087090 69843299 69843300 69843300 76776421 76776422 76776422 92069821 92069822 92069822 93217609 93217610 93217610 96713899 96713900 96713900 89652817 89652818 89652818 95995117 95995118 95995118 80927227 80927228 80927228 91116283 91116284 91116284 99154229 99154230 99154230 82646617 82646618 82646618 94186733 94186734 94186734 73572509 73572510 73572510 88073539 88073540 88073540 92601701 92601702 92601702 82641521 82641522 82641522 89676233 89676234 89676234 84481337 84481338 84481338 99248777 99248778 99248778 94180291 94180292 94180292 81030617 81030618 81030618 81633533 81633534 81633534 69577901 69577902 69577902 77157079 77157080 77157080 84972227 84972228 84972228 75701399 75701400 75701400 78808823 78808824 78808824 93864853 93864854 93864854 85779571 85779572 85779572 97834769 97834770 97834770 94363433 94363434 94363434 82120453 82120454 82120454 89956067 89956068 89956068 93860329 93860330 93860330 77756737 77756738 77756738 98045089 98045090 98045090 85111123 85111124 85111124 77325679 77325680 77325680 82560469 82560470 82560470 88648117 88648118 88648118 70624243 70624244 70624244 71933441 71933442 71933442 72250543 72250544 72250544 90428477 90428478 90428478 90599947 90599948 90599948 72586291 72586292 72586292 77710967 77710968 77710968 72549689 72549690 72549690 73550461 73550462 73550462 83249861 83249862 83249862 74872397 74872398 74872398 75319483 75319484 75319484 93169829 93169830 93169830 97514063 97514064 97514064 74276471 74276472 74276472 89984341 89984342 89984342 69946769 69946770 69946770 92194033 92194034 92194034 76643711 76643712 76643712 71847901 71847902 71847902 81247051 81247052 81247052 69953201 69953202 69953202 94095949 94095950 94095950 91554499 91554500 91554500 82305253 82305254 82305254 81267643 81267644 81267644 78608813 78608814 78608814 78244547 78244548 78244548 72965267 72965268 72965268 73525667 73525668 73525668 90336107 90336108 90336108 88516081 88516082 88516082 93753689 93753690 93753690 82806793 82806794 82806794 96617791 96617792 96617792 77585737 77585737 77585737 92451413 92451413 92451413 71098759 71098759 71098759 95007229 95007229 95007229 93925541 93925541 93925541 98070251 98070251 98070251 72438061 72438061 72438061 69118853 69118853 69118853 95467877 95467877 95467877 68119273 68119273 68119273 78625979 78625979 78625979 86943667 86943667 86943667 80207917 80207917 80207917 94094177 94094177 94094177 86093551 86093551 86093551 84727723 84727723 84727723 85654763 85654763 85654763 75372793 75372793 75372793 73498301 73498301 73498301 68632087 68632087 68632087 90634507 90634507 90634507 92280547 92280547 92280547 94383923 94383923 94383923 83016251 83016251 83016251 87751973 87751973 87751973 68811163 68811163 68811163 92132933 92132933 92132933 87871151 87871151 87871151 79609597 79609597 79609597 94387751 94387751 94387751 84234551 84234551 84234551 69316969 69316969 69316969 77506001 77506001 77506001 80880461 80880461 80880461 93562769 93562769 93562769 68152817 68152817 68152817 75120043 75120043 75120043 74513357 74513357 74513357 94701473 94701473 94701473 82405333 82405333 82405333 92708827 92708827 92708827 99672367 99672367 99672367 67875449 67875449 67875449 77915861 77915861 77915861 72296831 72296831 72296831 75824251 75824251 75824251 90211813 90211813 90211813 76512277 76512277 76512277 90235987 90235987 90235987 77237939 77237939 77237939 79600957 79600957 79600957 84965809 84965809 84965809 80976793 80976793 80976793 79959941 79959941 79959941 77229457 77229457 77229457 74089579 74089579 74089579 93944713 93944713 93944713 70295947 70295947 70295947 89475341 89475341 89475341 92821163 92821163 92821163 96241451 96241451 96241451 96611609 96611609 96611609 79680749 79680749 79680749 80421923 80421923 80421923 94057013 94057013 94057013 76794077 76794077 76794077 86276599 86276599 86276599 71822833 71822833 71822833 96743357 96743357 96743357 68495711 68495711 68495711 80621813 80621813 80621813 88749107 88749107 88749107 79880107 79880107 79880107 95487671 95487671 95487671 89158871 89158871 89158871 88734749 88734749 88734749 80593361 80593361 80593361 90796073 90796073 90796073 85800367 85800367 85800367 89542403 89542403 89542403 91399001 91399001 91399001 98640677 98640677 98640677 94240799 94240799 94240799 98619751 98619751 98619751 93276497 93276497 93276497 74189341 74189341 74189341 71447273 71447273 71447273 86554073 86554073 86554073 94423633 94423633 94423633 76137221 76137221 76137221 99835909 99835909 99835909 80406101 80406101 80406101 78754817 78754817 78754817 72613039 72613039 72613039 86605159 86605159 86605159 81374651 81374651 81374651 79751731 79751731 79751731 71997553 71997553 71997553 76979779 76979779 76979779 91866149 91866149 91866149 91175729 1 1 87252689 1 1 87900229 1 1 74341951 1 1 79132247 1 1 69898223 1 1 73782743 1 1 93091799 1 1 90049093 1 1 93150611 1 1 92120723 1 1 95156591 1 1 90377929 1 1 78980353 1 1 76183873 1 1 78222871 1 1 89845079 1 1 80443087 1 1 95024749 1 1 89511881 1 1 73880479 1 1 73898437 1 1 68470403 1 1 68389819 1 1 74032393 1 1 70193713 1 1 69220981 1 1 73199701 1 1 71718431 1 1 94028339 1 1 67874033 1 1 80024951 1 1 71413259 1 1 88888843 1 1 71495323 1 1 80113931 1 1 85463857 1 1 96724267 1 1 73767623 1 1 92371579 1 1 68543011 1 1 85291127 1 1 92950399 1 1 84770099 1 1 90039349 1 1 97009433 1 1 89346197 1 1 87188267 1 1 79586099 1 1 72674143 1 1 86452117 1 1 96842111 1 1 67934947 1 1 68888791 1 1 78740443 1 1 85080167 1 1 95955997 1 1 68882227 1 1 68391613 1 1 77360683 1 1 73670957 1 1 99815971 1 1 83552011 1 1 91610017 1 1 78609313 1 1 73189993 1 1 76702859 1 1 72605831 1 1 68741203 1 1 78157763 1 1 69725969 1 1 84992119 1 1 79510811 1 1 83929301 1 1 81435467 1 1 73384841 1 1 74241877 1 1 86286539 1 1 72222809 1 1 93333991 1 1 79259197 1 1 90686243 1 1 75463513 1 1 73090183 1 1 89682227 1 1 94963123 1 1 99287779 1 1 68846927 1 1 84017071 1 1 88106747 1 1 96897257 1 1 76944383 1 1 78120733 1 1 68503373 1 1 77526899 1 1 88213417 1 1 71000707 1 1 83517257 1 1 79555237 1 1 87992701 1 1 61258213 4681747117 4681747117 74755403 8677314793 8677314793 96243820 235867826 235867826 29990990 2368207539 2368207539 29315690 7120862804 7120862804 84265134 519682368 519682368 84474682 4078672885 4078672885 86983093 7929677241 7929677241 38129248 3871956995 3871956995 39536146 2163941084 2163941084 78709844 1490073035 1490073035 88481074 1095772169 1095772169 90465865 7481014695 7481014695 38459338 4507459936 4507459936 60117802 5097990907 5097990907 13407598 1254180046 1254180046 11608328 8649497287 8649497287 63482042 4184683392 4184683392 29690665 9199525954 9199525954 90196769 3013940599 3013940599 68640636 8669614925 8669614925 19810965 399163234 399163234 39627537 6897760037 6897760037 83375761 2002804223 2002804223 58183366 3972378023 3972378023 98480622 7687858124 7687858124 76978977 8573722463 8573722463 69172722 8147896848 8147896848 63823117 9965131669 9965131669 99085743 9138876379 9138876379 91975003 8755430481 8755430481 38094963 2092865101 2092865101 45757202 7143477227 7143477227 95638871 6848386691 6848386691 95765194 2015709525 2015709525 43372218 1120040190 1120040190 7453617 7665595344 7665595344 11612589 5647608723 5647608723 12012129 5695922872 5695922872 28512062 482723392 482723392 63228209 1015520674 1015520674 16679433 1809861337 1809861337 92438922 9710375277 9710375277 31011410 2150281871 2150281871 49161107 5479295264 5479295264 74839713 8154130178 8154130178 30039934 4123984174 4123984174 75168438 7978813567 7978813567 70990448 1204666392 1204666392 64069591 1635309632 1635309632 23763956 723565956 723565956 57694486 2888893191 2888893191 15365329 1407370706 1407370706 43963846 9086631656 9086631656 43176734 8418512034 8418512034 91554380 8507961426 8507961426 84713166 3247992647 3247992647 50920204 5925245370 5925245370 47992357 5764137912 5764137912 43737453 1561811803 1561811803 71764450 217066979 217066979 56830146 321983590 321983590 35812976 7977572073 7977572073 91509447 7037948906 7037948906 77831769 6643161843 6643161843 19933555 7501986943 7501986943 57146416 8010553927 8010553927 11512156 5593600101 5593600101 76580776 1035847028 1035847028 68221016 5570929434 5570929434 98239438 953901088 953901088 18404588 7830669391 7830669391 80181275 4046390754 4046390754 93311701 1496389876 1496389876 25874302 7515362369 7515362369 76180851 1414421171 1414421171 42884177 3592536573 3592536573 92017442 1778587680 1778587680 53248569 8769637629 8769637629 65766998 6003303378 6003303378 90019655 5194239060 5194239060 41734947 914455611 914455611 17767364 1440682688 1440682688 77230377 6619916406 6619916406 94947183 5186894856 5186894856 67804039 6575155360 6575155360 52098939 6943505068 6943505068 61532376 5522090656 5522090656 24009446 2378630670 2378630670 64717986 5308237476 5308237476 29835574 8314589520 8314589520 34811401 1647415090 1647415090 64741539 1899744285 1899744285 18120315 2784592043 2784592043 64800530 2778171063 2778171063 51287703 5135585347 5135585347 82563148 245314856 245314856 30126861 4000295262 4000295262 20487490 2051203057 2051203057 58382159 4960982178 4960982178 72568420 5686320249 5686320249 99545260 3774890064 3774890064 90696966 9426219601 9426219601 32422470 1782877759 1782877759 81410366 909307431 909307431 86801673 9078702504 9078702504 86845299 5549643756 5549643756 84482256 3825255522 3825255522 17115636 5438466297 5438466297 42168014 1382048693 1382048693 41984878 6403244756 6403244756 86945955 4731120535 4731120535 13222038 9212849994 9212849994 19865598 3795219086 3795219086 44876518 7797409784 7797409784 62706936 2053763406 2053763406 39176532 5608016432 5608016432 68390890 6679772631 6679772631 63403445 602230477 602230477 58812186 6651615290 6651615290 57900788 4506569222 4506569222 58343420 4749546588 4749546588 48032466 2561800715 2561800715 53578485 6876978742 6876978742 98609679 8000688078 8000688078 70908558 7479043188 7479043188 56085526 6171335512 6171335512 76142370 5113902108 5113902108 80895364 5049657774 5049657774 76909956 1030554357 1030554357 70588884 7663380236 7663380236 91306155 8466461253 8466461253 79430876 6798559534 6798559534 23581978 2946199682 2946199682 67510614 4426113265 4426113265 77048186 3427853939 3427853939 36054190 960414381 960414381 27155726 6645324708 6645324708 81800148 5236078834 5236078834 11225706 1977824382 1977824382 75085023 8997586151 8997586151 83836852 3181851389 3181851389 68332227 3636448648 3636448648 95761659 3785288145 3785288145 90929524 9512541922 9512541922 15617505 6041392577 6041392577 69533877 8211858377 8211858377 70247566 9812317745 9812317745 64637794 6720698902 6720698902 95480186 6341085458 6341085458 83777337 2665832544 2665832544 21019220 3690849376 3690849376 77132046 6932236066 6932236066 74611158 8730003965 8730003965 52053148 9670970823 9670970823 82770519 9126859300 9126859300 82529944 8518230824 8518230824 64929050 4042763895 4042763895 18300254 1321916949 1321916949 67449646 2177582172 2177582172 23204226 482451794 482451794 10976590 8171622592 8171622592 35043318 1442997214 1442997214 46401710 9556432012 9556432012 80780860 4728788555 4728788555 21512508 2197711235 2197711235 70436559 5171220337 5171220337 43678922 4657048755 4657048755 93346152 8603948067 8603948067 67110087 7667516877 7667516877 51615026 2796957132 2796957132 41780355 6305325330 6305325330 80995490 1145269273 1145269273 63706314 3095267090 3095267090 25382760 4532324270 4532324270 90225265 8312287159 8312287159 83274726 713698580 713698580 89062952 4201622103 4201622103 61606714 4137407117 4137407117 52663006 6009302758 6009302758 77942116 4327779207 4327779207 36468170 6968772 6968772 72510510 3576926953 3576926953 83975476 1401911795 1401911795 37786810 7016987315 7016987315 91099533 5345032368 5345032368 91828114 8087925572 8087925572 49967994 3655261292 3655261292 58205990 3436274526 3436274526 80957490 8206455932 8206455932 51885528 6028819237 6028819237 69957766 3979681823 3979681823 91267760 6032609936 6032609936 82535822 8580550874 8580550874 62658574 2893987298 2893987298 56133282 1258747783 1258747783 46816305 4127370249 4127370249 94230962 469170765 469170765 18431390 3001875879 3001875879 89965718 9760845848 9760845848 70448658 6583927153 6583927153 61064598 6949980409 6949980409 71269260 2894089184 2894089184 77538426 4971332846 4971332846 55078926 1519523662 1519523662 90942774 2251225701 2251225701 81260580 359352564 359352564 82586946 8950247900 8950247900 67750386 9857788229 9857788229 32774190 8102580728 8102580728 38736870 313757892 313757892 96815580 9337811335 9337811335 78530690 4182436252 4182436252 86799270 3206956694 3206956694 57334578 6870360599 6870360599 82679010 369380379 369380379 44422230 7581869547 7581869547 94352820 6701273888 6701273888 94772090 3221381024 3221381024 83372910 7525794267 7525794267 89145490 4358155166 4358155166 34420170 4065034484 4065034484 83875218 8792138986 8792138986 70659210 6577990525 6577990525 73960390 8459773900 8459773900 27695646 4455825309 4455825309 57154398 5793176387 5793176387 98462010 5114232741 5114232741 71883780 389754617 389754617 41459190 7534100117 7534100117 74146530 7659732931 7659732931 42036090 8136492741 8136492741 48556110 670056569 670056569 93365916 8134079048 8134079048 99085530 3307190621 3307190621 66273510 9737111923 9737111923 32771670 7254497799 7254497799 97294092 3832128114 3832128114 68855400 6645499086 6645499086 89443614 1178784245 1178784245 90627702 1192779154 1192779154 76209419 8212793707 8212793707 72200478 8077041749 8077041749 55430670 3745199340 3745199340 86795142 8278845773 8278845773 65452980 1227777792 1227777792 72832242 9513848512 9513848512 42773070 5193675943 5193675943 64363170 4584664660 4584664660 92865102 7329228020 7329228020 66748638 4389396613 4389396613 50914122 2748630899 2748630899 30306750 9996998292 9996998292 91625118 7034023698 7034023698 95970588 2763144262 2763144262 73154220 4387735192 4387735192 88878540 478158265 478158265 76380290 6655839239 6655839239 86680074 8781260073 8781260073 99939084 9581858344 9581858344 96507930 9395934930 9395934930 75862374 9598496528 9598496528 86444106 4069926648 4069926648 62243538 5621462252 5621462252 93037740 30746368 30746368 66069390 7580318402 7580318402 46203738 5152057164 5152057164 84943326 5295327394 5295327394 64023918 4962839342 4962839342 91230342 6657953991 6657953991 64940430 9232754453 9232754453 60936834 6191595511 6191595511 35088990 5957515441 5957515441 78742986 1353840397 1353840397 52315914 9255485206 9255485206 98684790 6402293710 6402293710 73999410 2005488086 2005488086 86648604 9936901727 9936901727 85308234 159595155 159595155 57871410 688547924 688547924 64639290 6675169859 6675169859 36462210 5343235045 5343235045 78570170 3521229031 3521229031 64844940 3565755518 3565755518 94476396 931838137 931838137 97710930 6089716387 6089716387 56855442 6666748083 6666748083 33467010 3155821916 3155821916 31802730 2334598777 2334598777 43156110 460609179 460609179 52972962 5879051409 5879051409 73684230 196170182 196170182 33967470 9674429089 9674429089 48019890 9947242518 9947242518 99453198 5715108499 5715108499 75518070 5609760128 5609760128 84257862 3368854821 3368854821 75218730 6138338008 6138338008 91812126 9143720816 9143720816 92420220 2050052036 2050052036 86356062 2614035189 2614035189 74598732 9751940003 9751940003 59309640 9831083996 9831083996 58342053 7130081925 7130081925 5950672 6079836912 6079836912 2479400 8420419131 8420419131 5535387 6728898644 6728898644 95895670 5166589110 5166589110 216070 4028958976 4028958976 22121055 9889376837 9889376837 25382760 4532324270 4532324270 86356062 2614035189 2614035189 74598732 9751940003 9751940003 59309640 9831083996 9831083996 58342053 7130081925 7130081925 5950672 6079836912 6079836912 2479400 8420419131 8420419131 5535387 6728898644 6728898644 95895670 5166589110 5166589110 216070 4028958976 4028958976 22121055 9889376837 9889376837 25382760 4532324270 4532324270 86356062 2614035189 2614035189 74598732 9751940003 9751940003 59309640 9831083996 9831083996 58342053 7130081925 7130081925 5950672 6079836912 6079836912 2479400 8420419131 8420419131 5535387 6728898644 6728898644 95895670 5166589110 5166589110 216070 4028958976 4028958976 22121055 9889376837 9889376837 25382760 4532324270 4532324270 86356062 2614035189 2614035189 74598732 9751940003 9751940003 59309640 9831083996 9831083996 58342053 7130081925 7130081925 5950672 6079836912 6079836912 2479400 8420419131 8420419131 5535387 6728898644 6728898644 95895670 5166589110 5166589110 216070 4028958976 4028958976 22121055 9889376837 9889376837 25382760 4532324270 4532324270 86356062 2614035189 2614035189 74598732 9751940003 9751940003 59309640 9831083996 9831083996 58342053 7130081925 7130081925 5950672 6079836912 6079836912 2479400 8420419131 8420419131 5535387 6728898644 6728898644 95895670 5166589110 5166589110 216070 4028958976 4028958976 22121055 9889376837 9889376837 25382760 4532324270 4532324270 86356062 2614035189 2614035189 74598732 9751940003 9751940003 59309640 9831083996 9831083996 58342053 7130081925 7130081925 5950672 6079836912 6079836912 2479400 8420419131 8420419131 5535387 6728898644 6728898644 95895670 5166589110 5166589110 216070 4028958976 4028958976 22121055 9889376837 9889376837 25382760 4532324270 4532324270 86356062 2614035189 2614035189 74598732 9751940003 9751940003 59309640 9831083996 9831083996 58342053 7130081925 7130081925 5950672 6079836912 6079836912 2479400 8420419131 8420419131 5535387 6728898644 6728898644 95895670 5166589110 5166589110 216070 4028958976 4028958976 22121055 9889376837 9889376837 25382760 4532324270 4532324270 86356062 2614035189 2614035189 74598732 9751940003 9751940003 59309640 9831083996 9831083996 58342053 7130081925 7130081925 5950672 6079836912 6079836912 2479400 8420419131 8420419131 5535387 6728898644 6728898644 95895670 5166589110 5166589110 216070 4028958976 4028958976 22121055 9889376837 9889376837 25382760 4532324270 4532324270 86356062 2614035189 2614035189 74598732 9751940003 9751940003 59309640 9831083996 9831083996 58342053 7130081925 7130081925 5950672 6079836912 6079836912 2479400 8420419131 8420419131 5535387 6728898644 6728898644 95895670 5166589110 5166589110 216070 4028958976 4028958976 22121055 9889376837 9889376837 25382760 4532324270 4532324270 86356062 2614035189 2614035189 56664084 1085509299 5313321868 93596965 3172229794 4205763201 86368728 8877207624 9687316444 9199674 4688278176 8291196401 51138382 1182502086 7773387796 4983521 5849508699 7003579636 52251510 9316085154 9846413195 77306695 4705601040 5553074253 12551608 8800310915 9962617547 61578441 3144318012 6389611495 40640440 7123851440 7665686757 12159932 9976424121 9979268166 70692182 2150081136 3896836263 59001284 408435615 8044427407 4384353 3654162590 6813496047 65352811 6028836324 7021525830 57592511 711652567 6938431023 23681558 6969570887 9569608022 74170373 1147400183 8731953636 81943452 9702871920 9836636307 10343859 9260809839 9875803923 52742415 8202836176 9822494724 30333482 2576105016 9901809648 64230474 1920926845 9388626925 69274059 2096349503 8424816057 57170418 7149843618 7849184840 33281768 9639587300 9775340018 2467103 5252192637 7932051288 39712001 2975982108 5479149800 93672416 9207061256 9620516385 52376981 5804932626 8252378711 7711381 4300610555 8317969497 68497837 9745381852 9803628995 95665007 8005915641 9422411150 22185970 9672696113 9686159786 33986115 3683206330 3871466350 92163670 8213040510 8669913220 18608954 2704612970 3735680601 11160749 3018896964 3369669151 49928134 1695861752 3641052585 50075324 4072476394 4925577845 49644050 8553507559 9483678614 18772339 9134632577 9516272012 64501544 8835861133 8873319922 27695060 6003575848 9715189244 41684428 2523523341 4260890725 45437242 3566282569 9685037654 57297846 1562192952 9541663788 25046102 1349281846 1546384987 2917959 6439897406 9049643579 2693545 1588145323 5844509603 43119769 8307790774 8857959700 80231508 3815547293 4718800866 92603149 4733469095 6664850511 56958306 9545590462 9756233641 48372672 8346484469 9738298346 91578336 1406527149 9970925870 6343637 9484214090 9986535848 19802504 4839370925 9877622288 81834881 2267021204 2628630813 25987924 4140383131 6796835143 39236708 8867855797 9236083776 67879319 3288756087 4200038507 17045729 3467196643 5551314893 79728112 4708280979 6727149806 93571531 6992650981 7577203595 57827965 4870777622 6189951171 24182256 7418922930 7556042460 29181735 2193622979 7934941142 4742375 7730302478 9627556118 80663699 4290956613 8168846020 405243 719258001 9951395879 59023067 3247078723 4159919565 80893595 7850744566 9716104025 91121055 4440715049 8981308273 72404906 9021249744 9236545784 88924174 5760428440 6025957155 80070345 5970376384 6569765601 59845409 3378431117 7959262157 12954484 1763572274 8642263208 50490561 3762949419 3966691330 80802033 6424433344 8277964087 95973223 4498164322 9586808250 94677985 2106334494 5922385981 90661919 7927458513 9360636688 14320743 8266613057 8394726310 10831539 3717652864 4913122507 26599674 7683956844 9785619701 42549045 1564596629 2350501895 26436633 8198649067 8712370538 66297850 3071871445 6321377983 2380741 5611629815 7345571248 36144147 9428383867 9537338112 51473032 2837997064 5216003790 77179899 3907529028 8944284949 40375668 7121054522 8877592526 50047998 7526814552 7894850887 72946964 8345449096 8560435689 11482643 6532353690 8214231416 73430172 9083092101 9708881122 54986208 6484379043 7116067464 6515846 4610026067 4682208707 37610962 24198707 4616420484 44822630 1571411936 3708348162 66793805 3773732171 6482844185 92584662 409352243 9573827428 75117512 9876881166 9876987907 15822797 2204788337 5516359603 15068702 6522690904 7925215946 19893951 9590159821 9748142068 49918027 180504699 9593881922 21080140 5342244652 7498747506 64002480 5544371889 5822476408 50923293 5578923814 5644833603 10976973 623849958 5088918221 61398857 194072852 501425320 87360805 4462467226 9238599350 77064778 722635469 1522931842 41582424 9207283734 9917545940 75400692 409287967 1260052743 36062712 6667949701 9684916392 43010292 129109041 5478819417 29014703 180915464 5659047562 90292503 4848514964 8052984274 26321693 3423622100 8240180350 87888442 435461953 1031271703 22652714 7102278244 9433976974 33211414 8999195601 9532973298 60246380 7552302518 9690593922 43951124 9416814170 9773333213 62044158 4942093390 8458743616 52380862 5616574329 8422366316 32161016 8259248585 9678122124 90589212 6529051007 9422834377 24767464 5761224622 7234841726 11516819 1205320716 1484458502 260873 295799006 5702283228 95233071 7873157672 9532905652 69123028 7400324838 9604983740 43266016 1955447352 4642478794 59345187 8508307952 8702648380 81082448 3302735563 3736403213 59625822 7338242414 8151105635 92214049 5214145854 9022229820 19416681 7260911889 9499725532 58045582 8720182855 8949900871 41649040 626627617 1190298146 74278687 7966136970 9160697457 14789487 7150782984 8766162576 85476773 8478585975 8567853597 10169748 7140749479 9689192603 57953635 282431290 9803871344 98046304 6664152424 7314578036 63195788 1480290609 5792038449 63726126 821586043 6155370372 41045091 7672673081 7964396953 35735466 9818742087 9986982421 67415131 6421317906 8323033721 50525608 2382389671 3946412528 84662757 3518575674 7958508126 52228086 4176022100 5176009727 10687008 8294666532 8505103099 53758155 7507445907 8180969753 17982401 755750142 1668684336 23425098 5944251717 9683206628 35590692 7686446098 8585797826 27588490 8678652921 9348755764 70131721 2397069676 5503463958 58594426 1275690447 9259722625 49586367 4525384656 4603791425 37751748 8253620216 9733066989 77369652 9017328834 9476560658 41871202 1499399773 5762106086 26920194 3479851655 8089836307 56629921 231983079 5901676905 44864354 5016611103 5672067511 80784159 2813415508 9711362123 16573256 9292967734 9431509455 58553947 4072249677 9436740967 34205001 3261114742 9727448269 88642026 1065542485 3540482575 41924682 7178458566 7317986006 59774718 3555711325 5416168186 24866998 1071183034 3668160891 40936129 7847590686 8944619176 54451264 8122206562 9594206319 89345553 341284580 1051793671 35553442 5955827521 6168165668 48955813 558094319 3837787170 81737072 4954389904 6470676029 36857086 9705927103 9782222117 24215204 1886104644 7356043132 83562210 2463517941 9079856908 1931895 1142935566 6196348678 99138393 3977770361 8424683515 35618482 13400373 1384148546 6335924 4671194052 7426312007 38314839 3632770889 9100567462 83141345 7564796908 8820149311 97853916 743680522 6155043915 77679573 5324153602 6410669448 28123673 7053482043 7894260834 23814512 8552458589 9553318956 78775636 8812130624 9653584472 44667286 1269572739 4762054783 59281627 5938673379 8261008450 48193499 8798916780 9251318188 7109394 6828099568 9445860492 2187192 4838940924 7358138834 27987736 7022838062 9899856352 53454313 3181949096 6476929828 44965193 5456673402 9081542896 55183698 8388108642 9793480057 10230389 520399024 5660532563 68664003 3289635343 7526296657 44664682 310791488 424481722 67647729 4126891589 4831113240 87566211 278759401 4324558343 10306570 6716108711 9206577355 83789862 8789335189 8797351831 67739287 1434572242 9682748758 73607160 3694562580 8223686215 58733225 5575225863 5747790407 55404543 2663619026 8561397467 54423031 1150814323 2617086828 18074977 9787120384 9952604786 83352617 9978128638 9999255344 29490696 1335090675 4100512872 84970436 8260740085 9356930619 37768282 2342388927 5174917080 83000298 3379972338 8926584702 64765431 384717123 550306131 31995335 1682721334 9908592668 53854923 5385674140 8884706495 30154571 8011412360 9296031097 59199054 213987486 4323559280 89270240 1400658172 5015394174 13663435 5017727179 8227874614 58335070 9880201471 9996651777 72640750 2835644449 5899878717 82811318 7568628243 7570569199 29029554 5973899362 6944408862 49265806 834158260 1352273533 24260093 5152193271 5438751446 92640407 4865577278 9216089368 77141194 2785119613 3186042970 15946472 6753077259 8022193761 69469653 1657236778 8193239106 88632670 1554630859 9304538864 60199167 1503659488 2357563356 63372741 6546056215 6797945620 2523046 1344405701 2309359626 20129693 6738460651 6847984352 17763764 5045591516 5074813522 28750444 4185645145 6781457335 52748952 2425238045 9815830929 77183209 4788289512 6261402959 55574555 7985811712 8390505950 83488235 9987283632 9988418875 54414770 8185034871 9748753246 69649158 1920850469 6711657999 91387500 3670377643 6794670726 46730624 4258420663 9349952516 84802146 3628382075 8691878487 82422054 4873531390 6483430967 84098776 6683934453 6788307913 5054054 1055788081 3976097534 11051568 4945884375 7646536145 18390808 8247190259 8899407883 35392200 1437537753 5509938337 4964036 4056089191 5541924927 48239726 7138938479 9410960613 8838955 5687374291 5786066749 54534009 5999028507 7562891158 31325140 2165642657 9765421932 44520682 3712530238 8369188914 7500125 3314894064 3811815466 93336991 520997350 1495398037 28769006 6281829138 9510080513 27719584 1350162523 1762274357
样例输出
3 3 5 -1 5 -1 7 9 8 8 1 100000015 200000015 20000021 124 -1 129 6 10 102 9380738672703581 5325303556229005 7820528758098761 6320243242501805 7021322068695569 7127874004893905 9368520426898805 7834422206089711 7795957844762561 6556847544230131 5836230784776755 6636218984129071 6211993934153411 7459809979746671 9851556513825055 5664546188449219 4790447605350539 8308301991262655 6362557882969091 6954105830212241 6514714524029741 8364044370067349 5490051760878571 8948224903428305 8115683694581009 4878086485046699 5894618898345661 8476852031041861 8689522720894489 9353578356496099 8037627685688305 9215062583838805 6549216150836755 8302177118852371 9831561227738669 6830463384191305 8871140767400021 5412914154127589 7756948360058059 8575075120695101 6829621075834961 8041826854746521 7137096385788905 9850319835244505 8869927307024971 6565960972431305 6664033791695621 4841084377143701 5953214916969319 7220279446311755 5730701886258599 6210830661454151 8810610722576461 7358134886723611 9571642123118129 8904457581908921 6743768883045661 8092094080064555 8809761453848569 6046110226643905 9612839575063009 7243903343432251 5979260710136719 6816231124060429 7858488736293805 4987783769947291 5174420006033921 5220141036045391 8177309542968005 8208350487002755 5268769713722971 6038994469786055 5263457446546409 5409670386862981 6930539439769181 5605875907398005 5673024594706771 8680617129059069 9508992580282031 5516994218490311 8097181715188621 4892550563486129 8499739812999121 5874258512495231 5162120949953701 6601083377443651 4893450400099601 8854047712306549 8382226378695499 6774154753699261 6604429880043091 6179345559877781 6122209213479755 5323930261346555 5406023781320555 8160612318251555 7835096684114641 8789754294862409 6856965049751641 9334997634337471 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 182351457 174505377 175800457 148683901 158264493 139796445 147565485 186183597 180098185 186301221 184241445 190313181 180755857 157960705 152367745 156445741 179690157 160886173 190049497 179023761 147760957 147796873 136940805 136779637 148064785 140387425 138441961 146399401 143436861 188056677 135748065 160049901 142826517 177777685 142990645 160227861 170927713 193448533 147535245 184743157 137086021 170582253 185900797 169540197 180078697 194018865 178692393 174376533 159172197 145348285 172904233 193684221 135869893 137777581 157480885 170160333 191911993 137764453 136783225 154721365 147341913 199631941 167104021 183220033 157218625 146379985 153405717 145211661 137482405 156315525 139451937 169984237 159021621 167858601 162870933 146769681 148483753 172573077 144445617 186667981 158518393 181372485 150927025 146180365 179364453 189926245 198575557 137693853 168034141 176213493 193794513 153888765 156241465 137006745 155053797 176426833 142001413 167034513 159110473 175985401 4701560271816247 9136275328507828 1135040798481597 7102486498717348 20875293531609943 7298516890568747 172272293458651389 23784400796708782 4613583895746632 3290532092770101 29320852577232020 4407048836093565 19336462964089677 5098640353427620 153239998922517838 8407769691288139 12550766546072447 10217389929476559 54627999459573997 20911358840963357 49590648200430782 527186859664022 91113740145797363 23855044614698087 115563158273905503 126184167318137108 219998786216553669 31311780943021240 37412093829897815 100614697117364849 9048089501528269 26575870792369097 163432758113874515 12357954876316778 13788198975005071 8096436775582010 19045462928068139 21861114000619694 7602234340974685 6881719184584159 5837231123141480 10062485168548542 149602760779541575 6668325125725238 5731233261731486 15647498573514309 61942102101551266 99959150865440035 5344986730700165 3379792537600761 4298696672451803 83336601025945355 3089243441263101 199741628335002211 181741919007622081 38947048170243110 15285982328039945 75428669840870205 39519217743478722 7589961814730310 311553631928580 3049728768456577 17856279349186609 214679597148883872 172349672715629723 29908246372497792 28610894939853585 16098593651930200 9915745128423836 47506802696460313 4259576634815803 36030053154441576 12977786751020993 19947239190162894 97227370296860289 3990806310695222 22008992741180267 7439138621405415 14150617124040227 17946323148179738 8501514956843247 12721584595967002 6399281996833964 8115209885350152 54720112063363441 7556300044430439 40194353841043769 14157801088891895 28554799947723978 57256401146652034 124035267157502667 3018357686884367 40997454361613573 3363842881096518 18002692964323707 87797453557688247 5063491484223801 13390700371751171 4202398163076692 26330254167418904 20632358122089542 18788616876826740 142488243707819618 1926841574087138 1276327554709194 37526017880324616 9450199772378801 6732625682907449 7756895359169257 4162730668880235 10339972440643975 27423448151648839 20302099575678494 12565712323048952 9208429060398862 5366048384759968 6102845371313359 45683552855061383 1090956169692941 65199332636679002 5930311612180672 13855234823425330 20508265069942755 8187950955808743 12522933004051543 12626853659469239 24723036571241056 12979482439217504 9283947310122398 6604989835316273 45079113890896544 51535993109577527 19286262467386562 4962655347373817 49801599614922336 4553616020097119 3462695301694603 6940709392842496 35692663401679492 3700410529603025 17322656725515102 6062642366948142 4359411005362575 17261209198657963 30891808669852101 6290092545407591 27190579902536025 14984586676836840 16708114481237799 9765284289924025 3545018787591258 3878935062177225 89116251604755047 108559275478469951 17978721600888501 19370116032577320 12553725643317453 5249852340348922 1727956960739178 6676231764341458 1865819601326940 8969646912836190 2809299128403373 44343469136082133 19099775589911597 3939854516109798 7142013778922745 14529628871040671 33464384903081087 15592953689440011 4246027060758898 17562575744715275 9276163460921016 4694950648862666 1386891227306 11538119561510931 9905508255392129 4252369296254286 9803536517494907 14384900684949476 12047005283224137 25413836198723 8645489680808074 2263964182469263 26514949634978259 23187135259579000 53049917022635339 30441008745179144 20001172641428262 22145794264652035 13033680196805649 6052379712789767 6882278917138549 15395704891187900 8242411530379110 11776272800714549 12881877505384735 3157886151465750 5532871506957027 10210937973400646 11043537044239920 10104701617993969 3437657016283928 9177836079643714 1992706371624514 2624776086159275 486686272038899 9476576179218535 10119216773966666 8851842574973048 405132977943078 15067417670841149 4692133029524174 9278713462467382 9378784219076911 1017999768427881 11226777514981147 10538061449702515 4361382670897001 20914904749800416 5550136754319714 4663968535963337 17558147738147964 15493180555804337 8938394070041414 4544941816792 7883458706135288 16785249399377327 466950197534458 10411915409237990 18931412928480982 11400869904184007 1084510682182308 9041012594934768 10923154546909470 21510409746632488 7924726343781239 4438608375330240 2060104717674 1351726041409146 1637859926459188 377788510692 13884903237574067 6919959881755034 17108648734502167 1339360694917843 16497964706963726 7404976964350237 9836113782973474 10312560971363210 4439181150563981 3332000322696552 23752867948397 8262726958775190 3156908899905414 5349684706693014 708299665868695 7262492364302726 9758456258567958 11400015966757291 30226064960078240 17337245961620104 8376690470437695 8330939601676939 47676181954149 16694226184907105 5667716262870897 5766696258920060 7565243112989351 14462074764033976 19985958911874708 8983237330771864 6968100702031916 2538223301274107 11528780462153408 21060293944925144 4946829167950277 10250212239647444 206284400309116 1328240622336742 14382601337575965 6494199934624549 3952333102550744 3853683146012779 1048055127465889 6611458929412382 9024776882435159 3520527633658462 2474884818848415 662602887637819 7415012381690488 481821435408663 10953852988787953 15922173105670214 7286991942214737 14121269661692368 3639131307360215 15390593507075250 19988191995259904 3157768955868258 9013193338719 1930884121117 275270352015 983951306263 401269236493 185249220964 148035770296 1632642159824 161158359248 652698871466 1386891227306 9013193338719 1930884121117 275270352015 983951306263 401269236493 185249220964 148035770296 1632642159824 161158359248 652698871466 1386891227306 9013193338719 1930884121117 275270352015 983951306263 401269236493 185249220964 148035770296 1632642159824 161158359248 652698871466 1386891227306 9013193338719 1930884121117 275270352015 983951306263 401269236493 185249220964 148035770296 1632642159824 161158359248 652698871466 1386891227306 9013193338719 1930884121117 275270352015 983951306263 401269236493 185249220964 148035770296 1632642159824 161158359248 652698871466 1386891227306 9013193338719 1930884121117 275270352015 983951306263 401269236493 185249220964 148035770296 1632642159824 161158359248 652698871466 1386891227306 9013193338719 1930884121117 275270352015 983951306263 401269236493 185249220964 148035770296 1632642159824 161158359248 652698871466 1386891227306 9013193338719 1930884121117 275270352015 983951306263 401269236493 185249220964 148035770296 1632642159824 161158359248 652698871466 1386891227306 9013193338719 1930884121117 275270352015 983951306263 401269236493 185249220964 148035770296 1632642159824 161158359248 652698871466 1386891227306 9013193338719 65502632017060 1022454680732426 38768640417295 3963191880663 941979133351830 34902479194314871 63273051202465 85857957982645404 15630848803282248 14572671927338684 7788414403895353 1046086765031016 12521626032725611 16217565658648 9957583799561085 658352305049797 874394954615263 1039546519733091 12219845198604517 26676957673696 1480481766363816 184682545852610 150178172488968776 186458130784670 194540393150093981 74790188544663253 164636276616519 19569179599509621 18574317827909 28161772038645299 2194076433129401 2878017447228 671527371181290960 2879846899541396 21489675360782933 33604327936141 9675623156245 6470198804203 217384096424472 4696957838622 1379161797661 86377344832646 178642674745444872 159329332549416 11658227096396 44403193919142025 220030690176541208 1248202290355266 1169067052212 800187584710827 3148484079807294 291781192576917 8295651927871 617186138450638708 92616413782058364 2453466885817994 9511665025716278 18974418116143 23034615183859 11321770523018195 44158901994858137 79393376155679 237377776450242 37204912423832 4238104379795 709010533690702995 5484296740549 543808376013224 3618333161994 33195813502034 1441850335884686 49776882195384 31024680136116 157194107104191293 124840185019783 47769364291775999 699541314451160 11689846726701309 19388762619986 314474673670356 357002219867257 591394310452902 920076876630113895 112143908325694989 14658757057328 1742291867015607 933621017869657 16850837130007 460698372148 76775238793387260 137401471879500 1589801985540609 144891240621023 2581567188687048 230106327428931698 307928174436077 5052704569629 156114439972654760 94321078670705385 6601145947037195 9720548159885 15254270758958132 86814003111335439 13631887848925 6661744754919165 153717373217829 92741834844317472 6343813546788 81011557419221 13315962068440 4585875560175 7903724865404750 1552714718963951 216287444420661 3694554629544 44683013280534 165888289974675 12719526765618 1321770852970532 7917402814496703 581094983713 25597044328193 5661911041246848 79225259306199 216895489224964333 45318430660905500 15264646445138394 86826320820403 351691034689801 4671653276962 418504799251434 10949076214054 47964773257426 1129100552296633 367182687381033 397585489903512 1487566030636882 10435023581596184 982128797639676 8848564586891 22905370542912 18934791221776480 81002720810359791 226872991093173 89487414524516 2182773424020463 914148977623 97206359297424394 124532105586228 892016373877464 2737119397336857 1925990133548772 722943635010783 2641169533998 21309892233477 2534095894088216 240806120164023 11450979610039186 5209264541247 74865463112670412 60963042587257 946805087435422 2665409031953514 10642868703112 21361153826530 25464531919630302 629059077941158 289977516099482 56947294157125 7531802775240 39808243994349 1198026798679699 120633148199813011 5185229120948458 334211491064792641 52636786523564 1881343339049091 2791255223646187 17824456063144563 110909116208644138 19564706722945 34013998964940 683011305514572 269866596882413 9767524143589 61364543627630 258877976565268 73931633723712 187881987258721608 6522441439647 38600648482574 16227431155387 8430356584943969 37996010106682 569323262726886 24650633682011269 1680440733950769 366643661997197 109687376847061 92768821916463 65837575255757 222015602425618514 94157511643461 25987449404846 2593996006136365 489726013395883623 388703385044152 12959720598582 2030846319042 4947750208296644 62567142160009 641047950140304 124573066352431 120388206593324 10133044558275003 6532773730303 68466536856701 14025373026176122 306081870795173 726942776659209 61272434152281 458569190814382 13503444944977497 158113429501197904 267220267846292 46558285200410 1012704583013142 559843022628039 2233312200539657 896544034591787 58486982983522 3960089877638903 3337134742320456 159495052538449281 280317820475241089 42658432236489086 38327642297066 116490248808089 988388954691528 601787629637 18439075178959683 24499874472507 15050804446287 48557172927072 1738854877946747 201122148673753 841608347745566 17247915373740314 1683023599077157 6758252417019444 12440240489336 2913307976144830 178321512560743 117989414436761 327123939040922 21573939957911071 2504010180904551 2953458095341 83423274454063 53047606826540511 38967886356697 16551817893762 50938541320583 859070502392675 453840167910 71361041554350342 324115566768919 53342236156790 246478000784683 5322600435855 1252475034227 226991071301329311 11525844971093 52047816965305 198628682130167 186300990793692139 7882834387348 12688721526083021 92609164050779 17150454059700