298
1000000000 1000000000 590348910 325201207 7416430 214112571
1 1 283735697 519044057 333944056 169023348
1 1 562082729 88664064 25209355 840890660
1 1 749037901 806299601 274126835 301928327
1 1 112571022 314445672 684374427 43115573
1 1 307439215 235675188 795267081 264051720
1 1 180492237 112861629 646280812 496348317
1 1 741291108 876584555 175508564 41307292
1 1 344445155 279994395 742345441 615658574
1 1 888993148 647282906 319412940 926411405
1 1 440869168 266193670 252238488 343754215
1 1 852954198 496899599 532352755 90014910
1 1 851683171 365768498 734310490 795931475
1 1 32583645 687142134 423786194 496761406
1 1 739806412 638467955 513706539 918364259
1 1 132417944 79140505 70709450 250602287
1 1 343335534 420778549 401281748 768088858
1 1 862072338 547485683 790385494 50684336
1 1 587525928 615939267 355110076 531901238
1 1 542444442 291328669 217465777 930767424
1 1 282639816 867982529 497907746 67647454
1 1 255329073 960560004 629108688 94517068
1 1 320236030 536290907 612520188 528985688
1 1 357642597 278135144 180561749 666283276
1 1 232690005 643149844 475855785 226768644
1 1 462232917 136975337 925874241 631899163
1 1 7718411 281272356 253572344 349206252
1 1 5075723 369988989 490366271 10446750
1 1 824661246 469256771 492809930 141204284
1 1 9080300 460893591 250993659 185992558
1 1 814467785 174718798 482969054 798899337
1 1 115396985 389992374 71740465 539178777
1 1 820018789 876709407 287104631 282338321
1 1 503874990 353979921 82872612 428885030
1 1 12753267 534695290 877810895 748519211
1 1 659219705 577166463 895747075 311587539
1 1 127922421 431093039 12443124 67877669
1 1 672688798 680853171 820538173 469867415
1 1 227970508 166382443 582212003 173361531
1 1 352957565 604188776 550428444 748221792
1 1 221772774 175183264 427689011 752403779
1 1 328903606 621412796 282497033 819732448
1 1 127649201 733787517 708379373 38183518
1 1 261447167 699576913 873098547 690917393
1 1 347565428 380548910 295515092 767316429
1 1 710071796 623510753 716408700 635493057
1 1 808894740 23665364 32585588 288113149
1 1 413195360 454301299 18595169 138024996
1 1 305580286 624543060 772312384 267811758
1 1 755366573 86078737 38484341 603282562
1 1 553886762 607144338 470080055 914050745
1 1 247892716 670229636 161587373 72040144
1 1 571648901 481412007 64515295 999813521
1 1 562325230 910409047 956027064 381569828
1 1 253649696 352439671 860616635 29565684
1 1 496801606 799313771 942305789 599213754
1 1 753225132 450008062 313587125 604274629
1 1 737720080 542568625 990843883 588693518
1 1 701004855 369090075 518886805 572823573
1 1 781579972 97102091 444790444 394900341
1 1 509153416 76465549 157478906 440037402
1 1 626642523 505009184 409968962 636485018
1 1 74489348 17363823 159029403 943445544
1 1 921478158 438284080 909645220 104922586
1 1 669337513 617504993 63928783 393126107
1 1 425636142 708115746 113804440 837776204
1 1 498076835 477971028 133107057 118175157
1 1 946967971 279059348 838741197 95375998
1 1 916668620 924129030 154323989 71838577
1 1 753984058 114058869 943649360 553996265
1 1 11762976 937913016 576569145 403105209
1 1 365673685 917324940 714200704 827781720
1 1 638802927 680129802 72146750 837653269
1 1 774685641 150186155 351059358 676864979
1 1 220702913 473790126 960150579 599508394
1 1 391191912 240103426 466215022 258697223
1 1 428134456 675896792 663048987 623842370
1 1 4053738 136049654 673104774 218424480
1 1 94209113 853093930 299071941 153855771
1 1 873109541 760599336 871568637 210418971
1 1 423173486 859507529 965989437 945203244
1 1 845450212 106683581 79023698 706786184
1 1 980261546 95520283 235979429 466278008
1 1 632912189 606934849 707837918 574853453
1 1 9736628 51453725 614595994 793383339
1 1 344528841 52074850 103919573 493464866
1 1 193149148 652242229 591712047 785327642
1 1 371595404 278910522 41751727 63023922
1 1 187688007 394472990 316655349 552187118
1 1 424721444 634439242 383787026 133007563
1 1 176650203 710639825 544006770 467154533
1 1 393906145 615700206 881875765 404246226
1 1 283400493 777432954 799442445 913033519
1 1 137929137 902763949 678746480 330912376
1 1 718604900 748258851 426195190 540948948
1 1 901581624 447162616 144664412 494621463
1 1 616736815 11718196 595947933 136966987
1 1 203873362 756505020 330166970 683297500
1 1 659736056 393139170 102630224 765595858
1 1 984839760 211584903 806296955 877659175
1 1 224888388 961156025 132443988 171578565
1 1 488407600 522186971 498919393 834983094
1 1 86140227 374129251 138503930 96012575
1 1 476308792 690440339 140216248 446727775
1 1 571462769 15643144 928851044 120348006
1 1 884578589 960148099 545654512 755662099
1 1 679590572 127654497 197035245 901620051
1 1 524834575 339968675 191997505 570653800
1 1 537228044 706337805 393318628 333803665
1 1 345299774 330751275 74094649 686477585
1 1 903783132 325231985 279903570 191914175
1 1 712910152 666275669 255734225 419818671
1 1 812639841 718241550 983458543 14045744
1 1 367819762 560170635 539698259 570580905
1 1 203930934 379280150 460294068 302582076
1 1 81826839 139486632 988752926 588512597
1 1 614212489 608375147 476952153 744664364
1 1 79525190 724123807 716383574 2395453
1 1 62731570 955024548 575305375 761382251
1 1 69135797 434115991 262794228 645672394
1 1 182232786 329761094 912253674 918467003
1 1 687274523 145850277 18895016 413107709
1 1 164791110 836825155 675447201 642910017
1 1 894697137 937420940 361108572 722821389
1 1 689075822 487578956 974816921 621461349
1 1 203745620 486229367 248394989 14353725
1 1 495890979 950508546 230064190 380418609
1 1 546320205 45650377 798472506 670579148
1 1 59468630 584981012 419273195 703260376
1 1 39995841 147432750 916108224 554921242
1 1 44650153 742750859 393191569 797115204
1 1 40886784 279131114 221856395 223843847
1 1 511584614 759452397 995424605 553307848
1 1 866139037 962198405 729054377 524712592
1 1 772857346 859448386 63406232 537696254
1 1 232434443 451685504 538007526 9046574
1 1 133679343 990708308 852149880 153189104
1 1 344650519 66411404 938034088 160302427
1 1 674627802 81390361 190813696 573219699
1 1 382489116 452224041 908110173 532990191
1 1 369082438 321927411 688102189 431735767
1 1 458096685 740756679 546671962 568180255
1 1 10469588 760045137 462104286 307395032
1 1 334633780 565989349 505184540 816196504
1 1 487987074 160272462 82587878 917277154
1 1 677320026 538838905 611551496 594383204
1 1 383378213 730116399 751281763 553224841
1 1 75200230 505378507 227750425 331016607
1 1 981234990 200499442 98470990 279564865
1 1 709980299 81008346 46677938 331889504
1 1 560612552 142578031 513708594 79360377
1 1 703654154 357647067 351539949 645991355
1 1 103720283 522305249 267708091 691999652
1 1 643379517 138528740 753025307 945529611
1 1 740089719 919012773 437677669 912108616
1 1 376751505 69367479 337283614 728339875
1 1 87203809 579755085 106727415 951305108
1 1 828902157 949200842 921531413 511293750
1 1 383451648 526727210 98873581 122384411
1 1 222063449 442679887 751056724 480520122
1 1 740760481 96466779 422449698 957484851
1 1 708857466 757715544 781626712 119855366
1 1 402004668 550957559 885193699 510557816
1 1 182059789 90194158 192318477 687126304
1 1 240613538 58122379 785208475 435419447
1 1 536467890 570820431 334912318 734743721
1 1 108611310 944507890 991508669 696969738
1 1 577388376 675554518 891449504 437904935
1 1 274458290 876560137 850235845 372099640
1 1 218359295 324150419 519000531 24454135
1 1 409434936 292511184 727423521 351599424
1 1 236314418 259252188 596202020 414296251
1 1 721669976 867622006 250223287 166875289
1 1 787310067 941463591 423833969 566716852
1 1 581683411 397461223 687220170 417172405
1 1 527680493 223040909 812384375 106061930
1 1 865440241 102638228 808343456 118293314
1 1 316506151 472664787 913152569 645458706
1 1 745270209 263087703 694769330 286205026
1 1 616941360 583962356 793775539 280685844
1 1 842550663 922274747 539742379 944302218
1 1 909444318 771496615 508263869 442985667
1 1 140203048 763013324 494929827 805304133
1 1 487318683 951143510 471458763 536878871
1 1 963865811 438573118 818983128 727754082
1 1 218979587 509695777 892284126 691799573
1 1 988886931 576413306 105147831 348903037
1 1 134074085 28267129 509957414 907722577
1 1 658142885 71888054 985618036 294056018
1 1 648100525 426783244 722321943 354438943
1 1 421395468 139327094 297169990 986636400
1 1 213815831 958066997 856132679 426515616
1 1 433140320 622881489 362301774 927364305
1 1 283599220 615777542 729196226 758985276
1 1 137765168 138745416 521761805 168494181
1 1 666105303 858225686 372852787 250428958
1 1 656217825 923355550 749422848 217564042
1 1 917910494 821347910 316532572 80173497
1 1 326010189 150991976 812730878 476078527
1 1 173033025 456114298 830710877 325210010
1 1 321559216 609989497 765756452 957054466
1 1 583303828 749652549 718240522 395872373
1 1 365503318 649437454 728590036 577609948
1 1 939976987 876773712 544700496 542683953
1 1 668457830 474337490 439167505 910288242
1 1 202303367 887511267 992603956 76908174
1 1 197646370 9013792 548718418 381930536
1 1 490093126 616749666 693110007 934298603
1 1 845605656 501678219 439937781 871589268
1 1 154840645 11205869 116512288 722832299
1 1 46171274 95774085 809166114 9420301
1 1 71980236 860344632 116200712 549950608
1 1 663575069 338378253 847539713 632570567
1 1 892682264 217302035 487236285 390956160
1 1 173426830 86265325 712693461 648998132
1 1 650664032 772798945 900244890 774686343
1 1 226975536 564846731 477575219 186366170
1 1 879486463 199304018 838790698 202729357
1 1 69384546 684531036 464103198 383758255
1 1 628484679 608907114 605969070 285922093
1 1 356991668 325447565 432620037 1182440
1 1 469630503 302938629 390148566 285460819
1 1 67868568 841987771 180192112 104237819
1 1 860419350 569985021 444453429 622351244
1 1 348744755 301401616 15300106 207562937
1 1 551792974 736297524 220167385 323197381
1 1 45102881 893089281 494184259 34690252
1 1 4321212 963508361 608593959 385342354
1 1 184375267 165085113 115945141 127861213
1 1 415692952 191649051 150629973 253642894
1 1 894984784 931376946 140778801 315514986
1 1 88156821 599375592 700789430 859940732
1 1 942422751 299346405 451248737 281790193
1 1 714370774 901389516 446835812 53807076
1 1 677852944 100856958 242375757 703932460
1 1 10241363 421977564 582512746 128622549
1 1 875414440 50393380 955712203 868595861
1 1 757933191 868151987 762337963 434197282
1 1 465475869 169588738 641983171 873517226
1 1 190813001 839263030 553851581 705871704
1 1 528627800 915251581 415084609 250229745
1 1 250374263 575668159 988794445 421416285
1 1 435182218 238881159 196379328 468048268
1 1 497056223 22382295 552149780 777553784
1 1 499346280 534825477 231693657 622633742
1 1 111047006 817166395 686943147 485873519
1 1 67679621 309687481 128744741 824006128
1 1 278643193 653316832 897671609 767410028
1 1 608043540 368660988 987878434 300689603
1 1 946327236 332974958 720061694 19930941
1 1 313621992 724089959 587825030 447292880
1 1 723694739 40615777 666194947 941368641
1 1 264195580 517875793 22273407 810750059
1 1 569407765 793656974 481098149 516118480
1 1 236126746 214672825 902440894 91246600
1 1 639333659 970059213 363234292 333746806
1 1 383018162 601534756 650161789 413395171
1 1 611059461 33563134 896193225 998616557
1 1 335911137 279997802 312341241 572699926
1 1 460281493 896556412 800400801 154262903
1 1 14041570 95388388 539748044 548232027
1 1 261887344 635864756 11229492 779414075
1 1 201553120 887454706 310436105 635806698
1 1 152155735 516112067 9276626 721722340
1 1 750185005 725075218 783327965 844096864
1 1 894284397 685212848 845075668 884831890
1 1 738485435 672840401 59147187 769948506
1 1 129925220 416740285 850659239 302263821
1 1 876667986 562117654 860994889 226782380
1 1 944995171 362306568 122301815 560447261
1 1 671580589 381094340 643786285 230731846
1 1 377978811 394482527 381236807 623222969
1 1 768654679 154677617 645218523 491244579
1 1 901076930 2434521 19185729 57036473
1 1 334403763 462389224 37254295 562502088
1 1 544991624 185023011 237964110 369097479
1 1 77754717 61439458 925310835 320185762
1 1 816590252 47559347 347216168 592799653
1 1 94827451 606201423 445048465 824703900
1 1 857900711 166965473 963454851 258876912
1 1 951151441 192242356 120822641 775239455
1 1 98947716 418398754 746096722 771448791
1 1 761254443 88215956 887715421 5395406
1 1 20097421 281589093 985089736 619193477
1 1 821756404 73433903 325290570 860144685
1 1 923525668 578241229 554459638 166634085
1 1 634376197 782343504 824911756 53646365
1 1 251606270 172520900 739241233 560967700
1 1 843996445 829208124 713584822 213031935
1 1 10949391 747782021 864163073 549853410
1 1 253096651 106729044 301686628 650807530
1 1 675509654 842169478 557636292 753065590
1 1 62643067 329942937 815155650 722104798
1 1 398245717 841739567 99369003 908789009
1 1 500472591 907462307 416614451 534827397
1 1 180166003 169298722 450652456 680555953
1 1 476387769 125895566 971511176 79617276
1 1 106855568 332626678 506901687 51047702
1 1 746245183 523159549 685645242 958038159