P15937 [HackerEarth] Rajat the Pandit on this New Year wanted to divide his Cuboidal Packaging block into cubes. But he loves uniformity so he asks you to divide it such a way that all the cubes are of same
普及-
题目描述

Rajat the Pandit on this New Year wanted to divide his Cuboidal Packaging block into cubes. But he loves uniformity so he asks you to divide it such a way that all the cubes are of same size and volume of individual cube is as large as possible.

Note: He will utilize whole volume i.e volume of cuboid before dividing is same as sum of volume of all the cubes.

Input
The first input line contains an integer T, the number of testcases. Each testcase consist of single line which consist of 3 space separated integers a, b & c representing length, breadth and height of the Cuboidal block.

Output
For each testcase you need to output 2 space separated integers, the length of side of the cube and the number of cubes which could be formed out of this cuboidal packaging block. As the number of cubes which could be made could be a large number so just output the answer modulus 109+7 (1000000007).

Constraints
1 = T = 1000
1 = a,b,c = 109

SAMPLE INPUT
2
2 4 6
1 2 3

SAMPLE OUTPUT
2 6
1 6

Explanation

In the 1st testcase a=2, b=4 & c=6. So length of the side of the cube would be 2 and the number of cubes which would be formed would be 6. In the 2nd testcase a=1, b=2 & c=3. So length of the side of the cube would be 1 and the number of cubes which would be formed would be 6.

输入格式

见题面

输出格式

见题面

样例输入
1000 6630 87501 3125469 89039 67985 1669206 82910 85140 1759479 6325 78557 1196920 92999 33885 4957226 91675 36363 4809385 64362 57839 7346676 32118 86393 3651012 17549 36045 440652 75862 9674 2849907 73296 60855 7913071 16071 40681 7156356 81266 66451 3994132 10469 42096 1523399 1281 10065 3493349 55028 59658 8921035 25763 52966 1348776 15215 70951 4505739 75487 58506 7351425 24806 5454 8637057 14331 79245 7803144 83811 47589 2926851 61189 30771 8876504 47404 26328 6516076 34556 59151 793069 31155 97571 8022961 26756 13806 1541202 30862 36750 3099570 39151 82405 6812341 21138 54898 3567821 28179 25888 6662991 93341 33888 1325176 34384 38442 9504264 33335 8001 1200940 85046 68021 2271346 82625 62256 961895 1576 26200 6910156 89400 55601 8255831 2341 63444 5219207 16612 44523 5971741 6500 29260 8653586 65881 90010 5402183 50196 54299 7702299 87916 83791 7553113 56467 61802 4327640 20645 86700 8930329 64551 47298 4963809 13724 80692 6093456 75166 54959 159522 1509 75131 4563130 12854 86157 2482296 41278 24169 9180541 34074 76556 6871693 5492 95886 4735700 69246 66017 1398056 8643 14079 4126148 69428 93278 548976 5876 89449 7140436 62037 41143 3856403 7249 80579 852598 83751 46499 2133514 572 88313 4169771 62256 88628 1273275 52139 39806 5595586 82626 69855 1540129 5203 71410 4837951 60764 6612 7682551 20709 58136 2771041 53238 95490 316626 47085 72517 705522 85753 24082 2506540 12439 33987 6561301 48441 57343 3066031 45676 91041 6463938 16251 30179 6964217 91376 31347 2401171 26103 38260 6121965 95025 56241 1630854 52751 54440 7453086 58640 8495 3298824 29135 10720 6470003 69886 68921 669801 10259 22789 9364674 47376 39101 825069 81191 10360 8049028 32721 76389 4376386 12136 50400 4999948 75339 98160 7567601 7120 61881 15493 94573 22672 5339851 29901 92313 3941661 63809 5013 6984051 74736 18705 606748 30350 65552 2193278 28535 44993 5869289 50176 74038 1297506 14637 3146 9208251 81983 82181 6904278 39448 63744 1420036 35873 60867 8864031 57144 40576 5352026 7891 72907 7124908 71591 70066 773271 4987 60168 3636556 23093 30701 9646 16326 47443 5676358 94335 53374 7431204 51606 66505 5649551 46349 10546 8113668 71481 26931 1004658 12826 2883 7963541 98995 29844 374816 42474 2778 301953 58234 63381 7436408 31000 58601 3387231 14940 14472 4548441 8454 79370 1627653 44957 69403 4444551 71414 3146 2293644 78372 76618 3145281 13487 18686 1907505 33713 83936 5342292 78843 57142 1048177 37209 476 7745609 41767 3791 8542146 59353 63981 6351573 84671 56508 4749577 49884 66162 3118564 57478 69584 6092686 14124 63689 4621486 51050 1506 6237691 45261 25343 1755177 24931 67916 8559981 27568 88858 3004115 79251 24478 3810317 59510 27087 8159186 73367 79726 2639730 98089 20126 9074875 84516 50037 1036881 57343 31438 4665036 53685 14402 1577365 89258 40191 9964213 30927 15706 7557420 72066 35828 3316499 85251 34855 5747166 43325 3027 2621191 51375 50929 3504061 4108 18301 1472521 41979 24586 7678625 29237 15338 6199704 11885 1864 6234741 30708 40862 7513726 97000 13848 9473930 37097 88002 4976436 16163 99211 2374195 34182 57026 7045182 56852 8101 4367705 25386 49356 1467482 44553 58135 6634191 57103 8106 9615262 38566 10847 6378021 92589 16192 2867961 55731 66440 1888801 39201 30866 7088658 17758 14336 192876 30554 83587 1147442 60161 7512 1523385 46633 25846 445537 15863 19494 5626285 66911 15439 8651505 88546 82004 386248 52191 19944 8153109 26883 97048 7544773 36511 32116 2852973 88406 90849 3908816 96409 29169 9602035 82915 92505 4737469 11098 90310 6920431 26855 26885 7976920 87063 83209 2415026 25943 91278 8623451 99401 95838 911905 95261 14276 7833882 22770 87172 5750426 24511 17126 305716 52301 96670 3317666 53161 24667 9535991 49619 92928 8431586 49826 48276 1479473 65611 96089 3369947 53349 59246 1675718 52766 99871 5157649 75763 19349 593309 17464 83886 7036773 17018 29951 6151481 47196 28004 9704663 30283 82029 3248881 45108 32624 9147390 31296 74946 583951 40116 89411 3381571 96901 47482 583718 86833 94414 933431 14551 91346 6432129 97280 66709 2410189 53296 31399 4501624 5204 3030 6859656 84351 50523 5040773 77212 14057 6613082 44716 43530 2177059 37719 81911 9232655 1901 33773 3795477 37959 49922 9331871 92793 98005 7911631 49817 4618 5920849 41126 36331 8747438 74395 91149 6850606 1852 14002 4341642 79189 53152 6620076 65886 26472 7564266 11951 5194 1982532 53607 18346 3651384 85784 68801 8015291 10695 79598 6194419 80274 8902 6047340 3986 82816 4664931 28403 54334 9261553 31207 9381 8038311 60291 2729 5456968 67824 9966 1184496 7251 56531 1504036 3037 90639 7906696 75126 38095 1126601 69921 15597 3258401 86696 33574 8687157 64833 85360 2277559 20693 83033 7593513 45902 84958 2319210 66301 10889 8459316 71250 60801 6872731 31682 31727 2271265 60596 57626 4062931 26878 96622 9702927 66446 36234 6576696 5105 59424 4818326 82320 89530 58724 333 61635 3245826 37250 20926 4665425 21121 45729 39420 2216 89527 6335894 54724 13911 101636 74285 47052 7632652 58685 60106 6728374 96361 69897 8191113 43746 44731 9459883 22070 45916 3066796 43853 12615 1001267 77251 10310 4302096 88037 66188 7131656 47129 62294 9915779 23756 29498 539525 18703 35571 5158442 31909 23206 9286785 3822 25036 8048870 56821 95930 3075419 58196 54963 1920764 43776 10614 638651 80541 38864 834531 32996 18544 2687526 91107 4073 1512638 13219 43908 1669948 15786 99163 9735288 68967 95282 7397535 89783 27677 7940421 84048 75610 7672372 94896 32507 7231384 43758 58296 5608213 15536 74467 3305527 87710 5386 5474841 27153 88681 3807539 6906 41872 101628 23402 33606 6572411 16066 55904 8101871 87316 93680 2199873 98618 11891 3743606 41969 20201 5211420 92054 88183 4816491 67603 22904 425947 59645 86401 4225947 4586 26157 8664631 62518 66771 8464346 29424 81371 8139094 70976 1941 9482828 76877 20154 5790154 79944 8282 6464616 4176 20917 301439 30903 65001 9343312 12429 74214 1398654 51545 37542 6938086 80375 84166 5788601 53436 89598 3093608 25395 67418 4151401 29221 14078 6395706 44524 32721 5826574 94270 64826 7091646 79391 20246 1177905 38376 60393 8466373 78889 29481 8449179 10551 18613 4368827 91681 56213 1125556 34811 78216 9331441 85601 92550 9168715 73757 67793 8764005 47096 46217 193899 67523 78179 3549665 58089 41875 9389511 66326 23776 550001 60638 57648 4157222 75678 30118 5294707 78414 2459 1431021 45000 90705 1201791 25706 50966 9446197 37541 6351 968451 25916 43031 2641766 20871 22391 4443306 40885 56425 2058532 46891 41416 711206 47974 51231 5230978 73546 43819 2664581 95688 31633 8353984 93941 64444 1008797 95562 73068 5118466 87916 27366 3252023 48980 28036 9462091 53567 83843 633742 86311 75551 1686339 11700 7647 118128 4446 93083 8326035 31656 8073 6012792 58804 3070 3772311 32325 93995 7948549 78306 34476 5188387 38976 49750 862433 37568 21896 5161109 14091 71469 2216290 60590 7606 3876240 72313 97821 5845484 79603 51551 809812 62604 53739 5771334 34422 14894 994666 53212 10066 3847710 41906 72115 7211216 5736 49219 14995 85042 71291 4348424 29095 95058 7218062 7270 45827 3481238 73401 99911 5374706 68371 59703 8482872 79711 10427 3453495 93551 36414 4970704 59286 50671 3346316 3554 43716 5598614 86152 77493 1685146 4386 93379 7914576 32128 47869 370404 62616 39334 4012334 26544 51595 2973101 57215 98490 5261706 11456 34132 928474 20731 40804 6352146 79523 16431 1661151 113 37646 1300313 79435 17106 6158311 46774 50984 4472166 17446 28851 8979286 13105 494 2332388 94578 22215 2922411 22093 50391 9352088 83258 71258 1496144 75715 84310 5231918 55774 37489 1247931 18511 24658 7385954 42706 20365 317501 43781 90938 6862674 91403 14483 8242431 28378 26655 6383016 26589 49602 1528606 67757 70846 7248251 42492 91121 4712989 69332 52517 7954691 70826 92165 7058492 17606 57334 7986447 72963 15394 6369539 65144 18708 7545884 19356 91738 2699720 87071 49386 481641 31232 60251 4292836 56256 63452 595408 99728 28101 2655420 69406 58037 8745815 91761 15806 2312335 97528 90040 3454919 55611 81246 6143464 35801 62460 5535386 98258 10926 5551141 22393 38670 1191180 38236 79861 9416955 36785 38956 287128 65126 65148 1867710 82194 76227 2815595 80426 33128 8330783 98589 67853 6355202 59370 10138 7920231 25238 75786 7197566 45687 53731 5290294 15961 69053 935195 8050 91269 2196431 21016 67955 5590990 39458 20031 8230035 90216 19027 9059927 20946 48833 1491693 61034 76330 464286 38626 38224 9877081 5008 44026 5040985 65674 28111 829531 7908 66146 1388139 14291 44937 412815 15031 9173 6553560 98392 9936 3881027 98636 67206 1018049 23011 51724 5954003 56059 59270 5259626 22474 72267 6842753 45380 80044 393474 70426 74356 1190660 79459 80786 3310193 62454 3013 8739914 24527 8725 2543388 85480 21297 2577476 35422 63636 1881465 21522 26965 7379406 57025 18879 5189309 19550 94527 7151459 97093 68351 5533526 26321 20266 7059896 81374 40025 1105331 58644 88166 7717531 19823 23223 1084665 73825 91536 8409846 65389 50379 1677001 84475 31609 3573533 8473 9883 9745728 48061 22195 9726796 84843 77532 9925743 91554 89485 8321354 45109 64335 753781 19741 61555 270410 67422 28126 9611892 73920 5176 1308151 57272 13265 6397022 57715 91311 5376541 97901 43097 692349 41944 15890 8089433 3510 45336 115040 38840 41897 504522 79244 77476 9772318 77362 52399 7811070 54939 115 7020886 50979 99437 8024011 47679 82434 6798468 1766 99651 3446198 20214 62533 1986341 31859 62481 408768 428 91783 3919041 46778 96121 6184847 47798 53070 331151 6878 81327 9499708 17261 26409 3756839 69742 39626 7744029 89956 67462 1595686 37464 11345 6600729 63502 28191 620861 76171 75393 5493783 32100 60874 3519374 6288 76640 177531 50370 47601 4368110 81047 6878 20498 60634 42726 3889444 22689 9692 6429179 48006 63224 1048375 88810 96446 8882187 95310 72305 4411138 49196 2421 5092471 73601 79300 5140791 83158 17137 6914951 74280 83676 2115204 47509 39373 6421051 67346 65532 1533745 83551 20296 1315220 35317 41126 5438369 24322 65791 4890698 60801 73303 7283219 57812 76179 1383332 62576 5188 3947610 35627 89256 3619256 44864 82990 2701107 97947 74008 1531096 67389 14068 3763428 60871 9981 4982683 8121 3100 5810788 56619 5246 7633803 26896 30478 3595921 56946 71312 2424100 34569 23306 7450846 55948 78795 4838522 75261 94101 2619003 86379 39111 8746896 95218 35878 4142248 46959 7052 825206 1601 83001 1273560 97341 33668 3889267 74811 53401 9085206 56265 30613 4744748 11682 34669 9956551 48070 64708 9031053 50026 85751 2978687 47282 79280 3045381 29611 83976 9965476 30575 63108 4746563 65452 26763 7231709 11273 15670 6039101 87616 98885 7530114 86636 97711 3941801 95476 84758 4912598 57661 65636 6401268 67501 343 2162226 14982 70177 569609 77070 23066 481070 4084 57225 5657576 12242 74802 9623419 10198 9788 6863647 19443 48328 4663666 92413 17316 5196137 83327 51608 747235 39054 3620 7642722 25917 62484 3448901 51076 17336 9187366 18679 5264 2360923 71016 54537 9099536 50184 92827 4872574 25640 58986 5776546 67551 47232 3642631 76185 5588 2513447 62716 496 2240828 67650 52368 3209622 76876 64501 5815234 19925 84382 5287560 93664 99136 4364333 829 44645 3671179 3604 20214 5279287 23809 6794 2441356 59769 27622 5184900 3843 4087 9011336 30465 56560 524580 10497 25665 5825241 64953 32321 6710427 71846 70451 9962034 19243 96692 9659634 60307 25184 9680531 25038 2313 5519479 28665 1558 86657 80733 75327 324310 90708 76641 2904742 18946 16957 7093851 58671 54483 2933559 83510 611 4756918 7192 40594 7817216 86346 10481 9871602 61962 84112 6217367 94683 20419 1384460 9366 60408 9745251 99365 59735 3323708 65161 61386 4308746 17790 24339 5287704 20613 48324 6922516 5775 55215 4905548 67115 24926 3765749 79169 38585 4455128 56765 23234 8450571 50101 63074 6148522 6376 85317 686929 42376 51169 7482969 52643 50739 1373096 57117 36309 5048220 31841 16617 3418919 22912 90884 920060 70829 10636 2940773 85416 22993 1562284 43251 64690 1440695 35176 93462 7687874 31431 95001 6047304 95916 60131 2790302 32294 42161 2929106 92377 6597 5343490 73204 36274 8490217 77948 82531 3725141 19085 9605 6120918 34170 56149 4919014 491 83246 5507176 49924 94371 6756626 41647 31171 5157982 137 98961 5464195 78996 84364 917921 73198 5423 3216904 23035 62194 8827845 24682 2127 2658084 86417 63173 2951613 69903 73086 7365612 52040 36610 7022235 73053 2476 1968383 69117 65876 1880552 55783 31992 7133929 76144 27031 3158606 8772 59617 3225168 62442 41756 4420340 65001 88296 59943 18047 15721 6547726 2461 46331 5033890 5697 40501 7173661 45081 32529 2675511 6291 48683 3142921 10255 8839 157059 83166 88185 8838061 65311 55288 5691803 68459 77611 887355 51551 55942 8514363 58664 37557 6694880 45511 12865 3913381 58416 8860 1553908 79091 77870 7696846 55397 678 3871198 82934 77650 3993112 44239 47871 2303880 54697 51807 7231503 34486 89760 1310072 25890 55807 5211985 91940 62906 1832988 47802 76931 9240913 34024 80616 936819 23286 88592 8165828 91586 90883 8539914 95506 79011 2726578 20005 13401 8057673 21135 50184 3804686 16911 38039 2590459 13509 83560 5737681 62209 16494 4901723 1268 36968 1410900 86886 47778 9412089 8356 42327 5062175 28242 52356 8152801 57083 2593 3270951 61991 91291 7573346 28894 64777 2113311 90445 46031 2439869 72076 39520 5269377 51243 88775 5109617 56671 58863 1898517 60926 32491 8147459 83672 6583 7108476 5471 40221 7034048 63561 82471 4218488 89990 67690 4433476 48601 59096 5482892 93284 41132 1081453 90430 58361 4034982 92523 33906 2079602 76945 88811 3265216 11226 12461 9197747 72003 47251 7457801 203 41257 4600536 27686 36976 8422697 96598 28544 369192 86092 29082 8852871 22832 87496 901881 83769 26366 3818626 25914 77329 3526484 51594 31162 864123 49726 31317 1711343 98945 16356 51435 42905 51682 9931921 58856 16156 8024244 42288 4641 2993658 39091 50945 6725577 2731 10577 3484716 64888 65826 1897047 43818 87307 5632508 18203 59758 349880 31331 36257 6994791 70353 57203 8582786 47375 93927 5890013 32938 46196 5177682 27388 68591 4755515 39153 20443 3751783 843 51125 67551 89251 23628 1136206 1121 34248 3861581 63585 76940 331450 7540 69985 3600017 68822 8746 7911037 27440 46466 6218899 80526 81468 1255771 12416 64806 4257468 45375 2666 9500736 74856 79856 9538788 52193 16756 5381484 16551 88953 6975253 86286 87475 2608247 88353 39222 6334636 14677 54621 743211 69631 73001 1859466 91751 41864 3842376 24224 15031 9266377 85948 23094 8451559 84171 32935 4311815 19549 34706 9563901 68151 77781 1927775 47926 98484 2794784 4779 10262 9599220 11178 39996 5804840 52991 80954 5690981 83616 66772 5419996 63534 4869 5345403 94771 58258 5116651 87849 17579 7157250 15922 43254 2002794 90047 53478 7300586 32916 51362 2224471 84516 60168 5152181 50998 34388 6351886 64669 30892 4175108 37629 42225 3929260 59211 48226 165920 25211 87656 8710576 52162 45468 6266562 7915 27872 3142173 47084 26795 633778 65931 11190 2428826 58368 72908 8936901 53801 30616 5438935 50038 31481 8334201 68093 53763 9427961 30355 79215 3319541 63563 40611 7915596 57578 51522 340161 64449 42161 3318108 23220 40499 4456372 32021 91179 9830858 24479 51978 988931 81278 98681 9374631 29477 18346 8801013 52490 68076 8816499 87200 69936 1299939 22741 95052 8068901 53393 71764 2384813 39257 41055 9281776 33753 19697 5133644 99777 34800 3815087 58139 8713 2750649 5866 79805 8570262 82348 78972 9038306 77328 61181 5936307 99476 19209 4324035 22496 70208 2635252 63129 2831 5027628 75512 83545 4372042 69938 57203 1715288 53178 30051 8387143 80755 14949 2886276 67643 97102 5729212 12089 97326 8245809 62106 91653 849901 95446 31034 5336933 58887 13101 9355365 84871 13078 1235767 73557 19113 6311080 71763 41346 4421876 90135 5796 7527511 36417 23469 3738410 3494 41514 4776397 82272 98464 5435411 49138 57558 1460501 15767 94473 4810861 6876 78047 8006181 86641 31649 7164362 31846 32308 3231424 52223 26569 4032946 88053 62963 6058051 53206 68681 5929368 27355 91079 2937606 29091 8655 2853901 75641 38992 9363027 24226 52001 1591770 3437 24380 134977 98951 21820 8363963 98622 35671 652636 86136 41251 7149756 91407 11078 1619359 51414 62824 9173885 22099 52604 8077980 29484 32181 8109815 73345 78280 2750840 45586 28206 839664 14257 53094 9951590 45788 52761 6583438 65095 49787 7174843 26851 34386 7241082 43868 88006 3726636 3995 88229 8420351 77332 26546 3704281 88335 53541 4432847 21230 28890 3268090 70421 967 1186775 373 89506 4736093 51561 78342 5249596 44350 33522 9316736 35502 3625 9325276 59409 20410 7559249 1650 74182 8071219 73336 68904 9322421 1938 52507 8990679 36521 33163 5406948 54975 92931 1944325 69549 11771 2901726 40418 65734 8298287 24619 56646 3172738 75761 45753 7484411 54026 94373 8151676 54951 47993 3797971 62845 40 370798 85930 21374 536936 91454 19637 256302 17641 73927 7871870 79786 40074 4911470 8818 92544 727526 20858 86966 6815796 81436 56491 60246 97329 57316 3134246 27871 40791 9431216 74341 22435 7732137 30210 28249 4653702 18551 41645 6135217 50621 73982 6999509 23019 76715 9796565 9066 59158 3135350 71040 86091 4042579 38351 15726 6038311 87780 36641 1116721 18415 9150 9230136 39447 83371 6600301 8236 76701 6586089 7906 34854 1937149 8193 46426 8724891 52088 48176 3700346 58931 84749 2582689 36215 94314 5561756 80376 51321 6256120 32571 86363 7394177 90171 24969 4969719 82550 95238 1041838 17104 93449 3550515 26121 42680 3904872 87026 35020 4631907 24348 62406 3667488 76402 97586 7167637 66190 67449 3363965 43486 90646 7427076 72314 74906 6284097 14138 24467 2841671 72240 88726 9110963 73146 81846 2250606 70740 89271 4316341 5626 21507 3366301 9926 60751 5363555 56531 10725 3601115 18749 75321 6325008 3652 10084 770393 52045 78435 5406342 4648 40970 4158682 70937 34369 3597724 50465 46726 4644991 59019 71526 6488827 77426 95514 8844513 40431 48032 3795899 89121 9883 5825288 32366 24236 9658188 57364 20781 9168833 98451 7094 2443352 99761 74112 8879968 21076 7071 9221751 36213 47711 5930571 16737 68668 6923811 95710 91348 3432134 78151 53546 5431635 22157 96405 5482802 24951 61828 6732647 10978 83651 9339037 86853 63776 1154596 30785 95251 3251061 71714 60876 1116901 80481 7777 4435504 15374 83315 2852330 65056 79184 947538 34509 77226 1257744 92185 23606 3643579 58796 95725 4775748 49401 20576 3276576 47264 17454 3210188 81649 48121 3475930 70426 67347 2122307 66189 65071 1933425 73547 66585 5756592 97692 74756 1956728 47161 6417 688587 86327 48544 5394366 72378 96242 8569335 46972 20642 539261 63158 89616 1983446 59321 85407 4614333 15597 96961 1506826 65014 79481 6759531 83639 53292 7265946 55866 88863 6035999 89539 6975 69780 48930 66357 2468781 5144 59476 8341065 93020 76798 9658350 28321 65614 516883 75556 91686 6712268 27841 58851 7255397 10211 53744 2800536 20298 16532 1421158 83236 97101 9132877 26249 34839 5500244 63525 88507 5608253 24719 95436 8344376 32872 42032 6661160 40318 55575 5858798 11036 67269 4033376 40228 42814 9425518 75991 26785 9588895 978 31643 378088 90900 13480 3916531 68837 489 7607068 1622 46746 7503766 19965 34806 6276389 41645 64424 4594948 62872 87135 9184662 71987 41762 5044823 13402 24891 1780893 50504 74384 9360908 82300 35857 1734914 73247 85243 3848685 49694 66332 6886070 17122 47720 4059908 38426 93381 7261951 86206 79504 111031 55102 87024 596033 17843 28256 2525329 89389 94116 5067358 47128 20023 6230154 61292 60123 8019851 2792 91143 5714798 54291 9581 1841232 48651 31076 8777364 91601 68396 9001025 39031 76041 6037146 91091 74158 5943481 52091 2447 7865506 78846 88536 6593187 11335 96729 5007983 2374 91393 3269718 56684 62278 5247057 52806 65836 8739039 43951 2706 467009 83720 53873 7314368 18767 8540 4376556 97652 73530 3728126 34030 60806 3214796 84153 35651 6281496 44086 35946 2011426 9522 61961 8992749 80423 48531 7072159 33461 31548 8511025 35302 58387 5037771 16943 83009 1705392 61981 48243 4058789 70150 26372 909124 54432 41289 9059278 94463 69971 4660012 96931 36675 8867485
样例输出
3 941214532 1 9086866 1 220253991 1 256919981 1 994976056 1 37537405 1 601378487 1 861803455 1 53264508 1 349483511 1 840363899 1 530233965 1 298539539 1 541359014 1 674079205 1 537613256 1 890233585 1 920661411 1 4881335 1 51048000 3 822011363 3 944775821 1 315598704 4 827550882 1 437275614 1 279740554 2 718030593 2 203579594 1 305223217 1 494178064 1 254669966 1 928864196 2 804932721 1 710292758 1 105041449 1 579654749 4 259866094 1 585868893 1 165187445 1 614390751 2 188727404 1 428009554 1 41243293 1 889344111 1 430962379 1 767281391 3 590383152 4 449447873 1 65390317 1 269103932 1 667127752 1 138205626 1 201363790 2 950000190 1 582836555 1 478257333 2 273101227 1 729702061 1 793676014 1 128274139 1 50059618 1 130702304 1 627297029 1 94726607 1 919235038 1 442392076 1 539903558 13 508289046 6 993123788 1 709019444 1 107264985 1 759008012 1 489061435 1 651966646 1 102894932 1 454280930 1 177834623 3 468252408 1 193237291 1 607860114 1 906836301 1 185448602 1 135482851 1 213480558 1 383732837 1 816216853 4 2696305 1 477348747 1 102963178 1 799194233 3 988592332 1 924690234 1 400128875 2 696118113 1 858795657 2 102940390 1 557496355 1 432460250 4 509416937 1 34281464 2 62371161 1 643991228 1 774233026 1 43483457 1 803601812 1 136273108 1 556478493 1 90166463 1 930938548 3 433435984 1 704443388 1 923900974 3 565601275 1 896108054 1 795687564 3 187522479 1 356883925 1 687870045 2 678120351 1 233071367 1 748140335 1 170470587 1 943498897 1 228913454 1 257755898 1 503043792 1 82835425 2 395789153 2 619265791 1 366765307 1 789721373 1 926537653 1 821240737 1 238157616 1 674633434 1 321975574 1 239287440 1 474242788 3 485977255 1 16713194 1 449503039 1 381218107 1 99211481 1 177169400 1 594712582 1 501520740 1 262941803 1 876045740 1 742865225 1 300355385 1 206640386 2 800700736 2 153374827 1 581665723 1 176073697 2 827078362 1 692429593 2 454622969 1 723921111 1 809167742 1 180112826 1 221444018 1 172243103 1 637335588 2 764835377 1 836994219 1 512948086 1 280241201 1 788889932 1 396876758 2 430835686 9 356814697 1 374798742 1 815154035 1 443296073 1 106219421 1 679341744 1 755271269 5 477411410 1 10891017 1 739342618 1 382507235 1 697816160 2 190030631 1 51008052 1 388460836 1 392997211 1 826783187 1 293781580 7 152012404 1 736639910 1 365721513 1 373033405 1 553068023 1 478512629 1 693858803 1 926028916 2 257214698 1 909765582 1 261119590 1 600862457 1 446800015 1 158884331 1 560051652 1 583620482 2 484776200 1 605033313 1 702513450 1 57057994 1 4072355 1 7908868 1 618342900 1 803762462 1 350600354 1 77025417 1 485662989 2 271803735 1 372393543 6 142942739 1 687345374 1 283209161 1 404885215 1 636382406 2 997677051 1 59044851 1 619548760 1 574614971 1 525145553 6 671734762 1 798934525 1 276690161 1 510557241 1 721764319 1 383092261 1 390517533 1 137545481 2 106192265 1 585302612 1 165671630 1 357938584 1 364284793 1 585711612 2 234932848 1 52331725 2 289140100 3 363304021 1 436780824 1 499612269 1 609218885 1 986321107 1 403592038 1 115856216 1 103821531 1 928510018 2 392699629 1 502611523 1 934584701 1 985722380 1 502719408 1 562491682 1 33941729 1 867506630 2 122903726 1 263748786 1 63988823 1 817594877 1 372550723 2 693664050 1 906584269 1 964222806 1 318543526 1 707063636 1 297462910 2 98279215 1 471841635 1 236787810 1 995867835 1 47832024 1 243421346 2 446068801 1 899850540 1 72968269 1 380153167 1 831286621 1 23953712 1 866583710 1 433002375 1 905779221 1 486289644 1 786782463 1 538314813 1 252303676 1 287396931 2 713726848 1 513190778 1 702833672 9 720934373 1 706644198 1 339079446 2 74916311 1 30981393 1 268098874 1 661951583 2 377053538 1 807587195 1 550913331 1 286950651 1 417804176 1 456233309 1 396138578 1 526307425 1 244252555 1 508234639 1 634175506 1 215179749 1 407695645 2 20029313 1 760592366 1 504495043 3 753153240 1 843588864 1 885595541 1 692822818 1 124691467 37 753613849 1 823504820 1 443986863 1 567198855 1 495033309 1 216923458 2 567949250 1 181656384 1 305904862 1 445790991 1 162791453 3 440750863 1 732393702 3 941723671 1 811688024 1 710662429 1 356532068 1 871541865 1 89882855 1 443247204 2 456993142 1 88046307 1 42188344 3 532698684 2 327818360 2 569688957 1 741598399 1 391129449 1 69902909 1 231614032 1 215996301 1 951925197 1 463204099 1 596913995 1 690593039 1 930674075 2 746764359 1 780240332 1 50754872 1 357686129 2 97619950 1 817443269 1 423175231 2 45663709 1 327762401 1 335803653 1 528862657 1 980303175 2 93068755 1 810577068 1 576595867 3 310282226 1 667270954 2 114075372 1 909417909 1 243370275 1 121834120 1 59349759 1 81310308 1 764018011 1 779821956 1 878824072 1 69516839 1 757529153 1 957701753 1 666009732 1 473726702 1 886353939 4 781978125 2 92679910 1 865456560 1 717915371 4 468945208 1 61489867 1 280343831 1 386128353 1 462115594 1 569943430 1 155812645 1 237525381 1 197705391 1 839011185 1 404686709 2 679835688 1 527696772 1 590896430 1 88442727 1 39126936 2 414113709 1 984833326 1 775351832 1 779262693 1 150164097 1 337417763 1 461650189 1 151377965 2 610294011 1 582025711 1 495514751 1 445009098 1 307778175 1 589601856 1 671857080 1 890731364 1 544667752 1 140712839 1 270738126 1 484845604 2 707125068 2 617515995 1 253930433 1 709012067 1 132168140 1 411833083 1 304857021 1 835028397 1 167835515 1 521146738 1 847976241 1 482974563 1 796679458 1 284914599 1 18377510 1 56823915 1 42348414 1 526537988 1 187986094 1 374400464 3 527093730 1 72499201 1 413831449 1 671024420 2 257008434 1 545954343 1 252428453 1 105670329 1 156825251 1 456738591 2 280180784 1 292061574 2 190847153 1 358972991 1 852124211 1 832211911 3 116661688 1 553556550 1 555899416 1 290449670 1 172486420 1 97600311 1 820398790 1 134608280 1 75839638 1 228536671 2 827082731 1 754560813 1 968243217 1 155471603 2 465147533 1 375483042 1 901707936 1 430990486 2 669222608 1 947575543 1 800492315 1 958817150 1 104015810 1 196982319 1 310374583 1 939255910 12 189553034 1 208884448 1 478957312 1 740869125 1 368225004 1 815752409 1 237884128 1 566673597 2 128597588 1 169784373 1 654140996 1 885876382 1 796078604 1 230698311 1 167954791 1 144259103 1 911847306 2 498106809 1 649966242 1 876396777 3 912112160 3 432937341 2 700212511 1 982089918 1 511264908 1 372210968 1 99203814 1 799325045 1 565216113 1 620940196 1 417516992 1 248252126 1 347725941 1 876246953 1 816222009 1 562461352 1 673648735 1 126303573 2 720848728 1 85032782 1 678758091 1 235588552 2 563374632 1 539218902 1 733874291 1 676177723 1 170985253 1 519983736 1 399915212 2 685461643 1 749291034 2 206785161 1 717669308 1 968691826 1 558522617 2 764606588 1 853722544 1 123285457 4 152200949 6 186914906 1 269549912 1 579575762 1 641924925 1 922020091 1 686042258 1 705792813 1 209978515 1 115090831 5 232012039 3 147495047 1 398322302 1 545450179 1 425386917 1 368582530 1 24683 1 107658900 1 612232460 1 315412994 1 497483868 3 620997325 1 884052947 2 525610329 1 979950384 1 209046612 1 47033073 3 407921394 1 622067035 1 172290840 3 304517541 1 220943040 1 523585995 1 429210739 1 189501047 1 185826806 1 694931094 1 453623636 1 509708922 1 407452708 3 121352316 1 515926651 4 506218775 1 811541861 1 23483039 1 870880540 2 356712386 3 744025645 1 418736840 1 437386592 1 930296143 1 161436866 1 698370594 1 193033912 1 926764895 1 131712643 1 543498185 1 995558667 1 681072548 1 691505161 1 893214910 1 90577759 1 724918761 1 976855884 3 544382222 5 219851869 1 594956051 1 84646518 1 60213791 1 902372819 1 890427994 2 605341847 3 946431077 1 424645062 1 108811221 1 898798761 3 922939766 1 917025558 1 447258103 1 328868329 1 227017806 1 218124712 1 153081272 1 69845069 1 704780755 4 399521258 1 270975607 1 967283082 2 838088331 1 783402188 1 362008204 2 980821877 1 189398043 2 542122469 1 596018077 1 941561036 2 224987787 1 812441920 1 425091380 1 406718266 1 717356461 1 52831123 1 349141899 1 597842106 4 383363419 3 946433028 1 375783216 1 519878458 1 796165198 1 735550195 1 666730527 1 599827961 1 665020386 1 863765517 1 565784901 1 186923769 1 371281303 1 857615523 1 587911329 2 241331546 1 408467989 1 157223641 1 257451133 1 857607267 1 112960921 1 936363420 1 951725929 1 275421946 1 558957358 2 328164766 1 811022592 1 482200167 1 445396057 1 307282566 1 951250860 1 626622559 1 544660027 1 467676996 4 895462073 3 412881312 1 937921640 1 763426886 1 969937713 1 548805240 1 670250990 1 155717984 1 558243872 1 335075815 2 599971463 1 215713637 1 21950342 1 338309248 1 906096976 1 847606877 5 236712036 1 797379533 1 301736321 1 328524112 1 598433960 2 496317339 1 650690893 4 807015753 1 778222994 1 603598308 1 538352029 1 401129273 1 754540310 1 234671662 1 502189187 1 253311965 1 611744116 1 232649631 1 855302622 1 687526568 2 49249711 1 884668205 2 62078440 1 281345614 4 537299739 3 874672393 1 267704360 1 712669289 2 70841268 1 958317571 1 921762512 1 790900929 2 63610062 1 772026897 1 364999520 1 163784618 1 838373389 2 46429960 1 977097952 1 320219752 1 820653777 1 604791241 1 202769954 1 13454945 1 949374909 1 44887314 1 945331982 1 68304583 1 769092680 1 286227169 1 173539071 1 595617127 1 605615881 1 151531354 1 120622221 1 900935796 1 987441454 1 585042744 1 400419946 1 101311499 1 66116928 1 795250769 1 257681717 2 368159731 1 150196118 1 130185335 4 43548993 1 615112276 1 745109906 1 898037209 1 205811517 1 109172303 1 397141134 1 525894698 1 473514769 1 232841387 3 471131374 1 845062036 1 382137275 1 663302813 1 786769280 1 994443174 1 978782947 1 313476101 1 47712013 1 812083736 1 386818450 1 131523430 2 667161953 1 508404754 1 447290714 1 193815861 1 551355655 1 623162171 1 263863766 1 989223109 1 270757450 1 884968606 1 773202673 1 214711421 1 836117403 1 328429696 1 724437761 1 952024723 5 406836702 2 860689250 1 37610451 1 475565749 1 207197022 1 802092 2 345990215 1 976998378 1 726588968 1 826729630 10 432985695 1 943594220 1 958934815 1 212751527 2 729494607 1 55100202 1 256433692 1 620050267 1 25331493 1 596002168 1 980232790 1 390427343 1 701838844 1 223810686 1 456446826 1 523806436 1 894155155 1 625963310 1 112005876 2 633212043 1 195889780 1 330634607 2 478904436 2 470612740 2 911248897 1 761284611 1 283990211 1 990503064 1 874074112 1 915977227 1 94884108 1 754480178 1 336522072 2 381782353 1 490598371 1 594429622 1 190710246 1 522239236 1 281740415 1 538512346 1 491454332 1 218683541 2 86256942 1 461912946 1 823755150 1 26735077 1 787448249 3 605922598 2 860645811 1 632198643 1 182858892 1 678326609 6 101857391 1 803111824 1 117986393 2 663938337 1 796171169 1 42798441 1 449907880 6 332228885 1 45249365 1 971473770 1 17004323 1 913613766 1 673447494 1 84081227 1 543118178 2 477401803 1 484578568 1 856630578 1 645334822 1 343715794 1 690670046 1 690018093 2 340722752 1 138911614 1 864407440 1 568991073 1 750221282 1 45334795 1 419277706 2 844925091 1 593756884 1 923548572 1 356359131 1 729673476 1 295752833 1 719477491 1 620670987 1 203133153 1 144532758 2 727731950 3 619161047 1 835192663 1 643177177 1 487648277 2 908630420 1 466997704 1 206626941 1 292014458 1 885065713 4 938363380 1 553861703 1 270417414 1 112162339 1 317838209 2 934783583 1 734350135 1 24242824 1 737179411 1 226065273 1 106710990 1 18849440 3 874846877 1 310036039 2 617898522 1 944145509 2 630156035 1 252855042 1 90513278 2 632978809 1 629728692 1 110584900 1 685692108 1 123714487 8 711328645 1 520340757 1 412749084 2 631693535 1 312104899 1 634053252 1 729698650 1 743026483 2 828964323 1 920305999 1 121555334 1 513100984 1 694231863 1 634940924 4 138826509 1 133986905 1 223499613 2 120470823 2 484686297 1 811110721 1 582513719 1 304484119 1 678812439 1 805662921 1 51134047 7 166838678 1 814666531 1 43607299 1 614725115 1 339797007 1 204216671 1 999199070 1 905725439 3 167181498 1 783089269 1 841485136 1 889353790 1 868249757 1 36595860 1 194014810 1 412990063 2 894073978 2 303698284 1 502272582 2 205918113 1 704213273 1 296286588 1 69707389 1 46792660 1 935768411 1 339122492 2 446238262 1 406622281 1 970618875 1 143857213