1000000000 1000000000
1000
909404004 181534702 2
484518608 606420098 1
218950493 871988213 2
97788554 993150152 2
981985048 108953658 2
390063590 700875116 1
123392422 967546284 1
504817801 586120905 2
715878815 375059891 1
807461935 283476771 2
404479489 686459217 1
927014680 163924026 2
996538867 94399839 1
522703801 568234905 1
433431130 657507576 2
445410511 645528195 2
607815416 483123290 2
639524401 451414305 1
571609687 519329019 1
516029918 574908788 2
785079961 305858745 2
485599719 605338987 1
635179935 455758771 2
925966779 164971927 2
256725337 834213369 2
698511924 392426782 1
353989540 736949166 1
891903367 199035339 2
633901114 457037592 1
733578572 357360134 1
454423199 636515507 2
749686653 341252053 1
926865313 164073393 2
359911907 731026799 1
186944240 903994466 1
133808057 957130649 2
697447336 393491370 1
594438165 496500541 2
157288519 933650187 2
472740701 618198005 1
183787658 907151048 2
800638501 290300205 1
249932290 841006416 2
491060783 599877923 1
441030094 649908612 1
342191122 748747584 2
841376265 249562441 1
113214330 977724376 1
281082971 809855735 1
128020731 962917975 1
308161364 782777342 2
134405116 956533590 1
345955913 744982793 2
808831712 282106994 1
194926036 896012670 2
98502519 992436187 2
539735045 551203661 1
724524025 366414681 1
709982997 380955709 2
735497949 355440757 1
530608588 560330118 2
855929884 235008822 2
935998914 154939792 1
251595536 839343170 2
623204854 467733852 1
306825091 784113615 1
97352928 993585778 1
483873953 607064753 2
732330539 358608167 1
232635430 858303276 2
278326028 812612678 2
161105319 929833387 1
631371554 459567152 2
349604650 741334056 2
480725246 610213460 1
772629503 318309203 1
880373842 210564864 1
108557970 982380736 2
972750451 118188255 1
313593431 777345275 1
868164954 222773752 1
245465998 845472708 2
522498174 568440532 1
894519243 196419463 2
98563659 992375047 2
390798553 700140153 2
151602285 939336421 2
678356063 412582643 2
253358336 837580370 1
238833535 852105171 2
994714852 96223854 1
958856894 132081812 2
251412123 839526583 1
311637758 779300948 1
120466227 970472479 1
854363576 236575130 2
288454374 802484332 2
888740122 202198584 2
611640782 479297924 1
388361101 702577605 1
834668428 256270278 1
555836462 535102244 1
218577288 872361418 1
656753292 434185414 2
842842103 248096603 2
645214735 445723971 1
939665951 151272755 2
333420265 757518441 1
642148539 448790167 1
785089544 305849162 2
414184675 676754031 1
487607819 603330887 1
438912159 652026547 1
793931087 297007619 1
204690349 886248357 1
307890050 783048656 2
576776353 514162353 1
664276823 426661883 2
254092362 836846344 2
616697574 474241132 1
495406877 595531829 1
932622672 158316034 2
250217683 840721023 1
800217514 290721192 1
120111058 970827648 1
953974737 136963969 2
532486557 558452149 1
529833042 561105664 2
211942630 878996076 1
870103420 220835286 2
499515252 591423454 1
403632018 687306688 1
894578506 196360200 2
304217149 786721557 1
308667665 782271041 1
335729728 755208978 1
761254234 329684472 2
300380563 790558143 2
271757419 819181287 2
892197558 198741148 1
504272880 586665826 2
265003650 825935056 1
274884347 816054359 2
942785739 148152967 2
132493824 958444882 2
125380466 965558240 2
445568825 645369881 1
426019963 664918743 1
772048747 318889959 2
229866009 861072697 1
800331079 290607627 1
462975271 627963435 1
449782245 641156461 1
450019429 640919277 2
946818770 144119936 2
355962935 734975771 2
164563899 926374807 2
942486534 148452172 1
707288907 383649799 1
216003698 874935008 2
472814241 618124465 1
355660971 735277735 2
253194892 837743814 2
125629797 965308909 1
580892308 510046398 1
140869046 950069660 1
719926821 371011885 2
296436413 794502293 1
652795660 438143046 1
993488128 97450578 1
707468107 383470599 1
286916951 804021755 2
435482074 655456632 1
610049588 480889118 2
793847711 297090995 1
574015628 516923078 2
922124338 168814368 1
410575810 680362896 1
829352324 261586382 1
212163950 878774756 1
682214824 408723882 1
969488422 121450284 1
572655315 518283391 2
650431618 440507088 2
883581679 207357027 2
930859780 160078926 2
258360912 832577794 2
242579284 848359422 1
898209971 192728735 1
967605539 123333167 1
618597697 472341009 1
370569876 720368830 1
72263174 836738217 0
950036799 140901907 2
964397644 126541062 2
522005555 568933151 2
612021567 478917139 2
797951934 292986772 1
783598271 307340435 2
203226201 887712505 2
775828144 315110562 1
864653641 226285065 1
200417488 890521218 2
965944369 124994337 1
694085290 396853416 1
646511056 444427650 2
108108142 982830564 2
200941772 889996934 1
280544714 810393992 2
469414322 621524384 1
105742064 985196642 2
393115356 697823350 1
389431774 701506932 1
450252144 640686562 2
664141224 426797482 1
107711019 983227687 2
459917868 631020838 1
352300290 738638416 1
693369358 397569348 1
298407290 792531416 2
610132176 480806530 1
841047379 249891327 2
529597264 561341442 2
390367872 700570834 1
119205029 971733677 1
131113698 959825008 1
951108605 139830101 2
377844052 713094654 1
528759522 562179184 1
719149352 371789354 2
850264849 240673857 1
191999208 898939498 1
661788640 429150066 2
183943014 906995692 1
268532051 822406655 1
143951113 946987593 2
762741815 328196891 2
793768475 297170231 1
734019102 356919604 2
587772455 503166251 2
972332475 118606231 2
537208056 553730650 1
682976352 407962354 1
291226184 799712522 1
752241218 338697488 2
583034571 507904135 2
355354442 735584264 1
156811015 934127691 1
240496411 850442295 1
235702582 855236124 2
583414713 507523993 2
699375751 391562955 2
527964832 562973874 1
732037235 358901471 1
344710809 746227897 1
113158415 977780291 1
104959774 985978932 1
198562773 892375933 1
362042034 728896672 2
158491896 932446810 1
548913171 542025535 2
313663269 777275437 1
554320573 536618133 2
522874538 568064168 1
305102124 785836582 2
543183601 547755105 1
304240455 786698251 2
625281767 465656939 2
762243420 328695286 1
93190824 997747882 1
591346179 499592527 1
923073330 167865376 2
653532845 437405861 2
993151687 97787019 1
951495383 139443323 1
591680501 499258205 2
740328474 350610232 1
231059581 859879125 2
629839774 461098932 1
368588237 722350469 2
558215247 532723459 1
342751418 748187288 2
163694511 927244195 2
121555056 969383650 2
713134297 377804409 2
709126838 381811868 2
468664532 622274174 2
108800282 982138424 1
118282543 972656163 1
416900096 674038610 2
824325251 266613455 1
583065142 507873564 1
670998877 419939829 2
320906524 770032182 1
950370312 140568394 2
296757836 794180870 2
214870243 876068463 1
915435435 175503271 2
582290489 508648217 2
748398142 342540564 1
797161250 293777456 2
637918361 453020345 2
940000870 150937836 2
690518096 260222041 1
502101535 588837171 1
680197996 410740710 2
320026690 770912016 1
354534652 736404054 2
676558025 414380681 2
508058336 582880370 1
947101499 143837207 1
753008150 337930556 2
584877309 506061397 1
476492296 614446410 2
371346305 719592401 1
184007216 906931490 1
672522390 418416316 2
263193945 827744761 2
241870453 849068253 1
442931891 648006815 2
220202921 870735785 2
304583859 786354847 1
229533094 861405612 1
125253862 965684844 2
106702004 984236702 2
252600223 838338483 1
484061693 606877013 1
452978227 637960479 1
343004932 747933774 2
242400214 848538492 2
945198417 145740289 2
288776661 802162045 2
643801396 447137310 2
184258477 906680229 1
879699180 211239526 1
348686603 742252103 2
370406457 720532249 1
988441443 102497263 2
617608448 473330258 1
553099985 537838721 1
398602311 692336395 2
512041704 578897002 2
120540703 970398003 1
154490751 936447955 2
828892022 262046684 2
891346024 199592682 2
653790617 437148089 2
503414876 587523830 1
469722000 621216706 1
527754865 563183841 2
436852941 654085765 1
900875356 190063350 1
488614327 602324379 2
95772688 995166018 2
626332865 464605841 2
403223836 687714870 1
601833899 489104807 1
898250103 192688603 2
997646898 93291808 2
112344129 978594577 1
285718507 805220199 1
321211023 769727683 2
990295079 100643627 1
374467734 716470972 1
251982386 838956320 2
747961224 342977482 1
135090792 955847914 1
183144812 907793894 2
180895935 910042771 2
251303438 839635268 1
122221019 968717687 2
840932142 250006564 1
618012424 472926282 1
325661931 765276775 1
466122210 624816496 2
155671878 935266828 2
845723996 245214710 1
305042943 785895763 2
311969357 778969349 1
273453223 817485483 1
745945009 344993697 2
286659814 804278892 2
190554442 900384264 2
756544478 334394228 1
357698888 733239818 2
892248252 198690454 2
406641824 684296882 1
263620370 827318336 1
756464301 334474405 1
531788301 559150405 2
305131476 785807230 2
572307547 518631159 1
115635152 975303554 1
537577044 553361662 1
955941365 134997341 2
118181463 972757243 2
576959280 513979426 1
303131825 787806881 1
365093017 725845689 2
695853994 395084712 1
187972259 902966447 2
312514937 778423769 2
166688416 924250290 1
684365157 406573549 1
516097264 574841442 2
603374472 487564234 1
317430342 773508364 1
248311677 842627029 2
224073990 866864716 1
896277768 194660938 1
293927837 797010869 1
892999264 197939442 2
150884067 940054639 1
867552852 223385854 1
166209366 924729340 2
727428846 363509860 2
452974275 637964431 1
976004730 114933976 2
158236275 932702431 1
914771373 176167333 2
344564463 746374243 2
187272260 903666446 2
202519510 888419196 2
119168650 971770056 1
465635488 625303218 1
91718562 999220144 2
283762850 807175856 2
390649296 700289410 2
980804662 110134044 1
605020535 485918171 2
359780000 731158706 2
470463088 620475618 2
374554887 716383819 2
459759793 631178913 2
700959428 389979278 2
386053335 704885371 1
617782179 473156527 1
788785867 302152839 1
995932225 95006481 1
623472384 467466322 1
460514086 630424620 1
278883057 812055649 2
176053222 914885484 1
731585469 359353237 1
433847926 657090780 1
636432906 454505800 2
760584655 330354051 1
922495166 168443540 1
773789286 870524943 3
856264798 234673908 2
754058910 336879796 1
115339051 975599655 2
576413281 514525425 2
954499092 136439614 1
718737539 372201167 1
197064453 893874253 2
377394421 713544285 2
369308397 721630309 1
949999175 140939531 1
609511244 481427462 2
268213948 822724758 2
953826649 137112057 2
881988845 208949861 1
941290223 149648483 2
288103487 802835219 1
415708822 675229884 2
930932301 160006405 1
660022654 430916052 1
614691082 476247624 2
969017436 121921270 1
625491912 465446794 1
623867191 467071515 1
592684328 498254378 2
325823349 765115357 2
235308629 855630077 1
538179721 552758985 1
596522709 494415997 2
129680115 961258591 2
590230568 500708138 2
204889987 886048719 1
131623621 959315085 1
316677409 774261297 1
732559475 358379231 1
482538930 608399776 1
247985713 842952993 2
527631913 563306793 2
327107547 763831159 1
363070739 727867967 2
732670325 358268381 2
139958868 950979838 2
524677656 566261050 1
630510980 460427726 2
306138389 784800317 2
202655791 888282915 1
440973597 649965109 2
893178479 197760227 1
554285653 536653053 1
606177485 484761221 2
612807627 478131079 2
164679098 926259608 1
435317422 655621284 2
656756520 434182186 1
500183600 590755106 1
849205775 241732931 2
383927715 707010991 1
435749833 655188873 1
411175566 679763140 2
779126004 311812702 1
230833845 860104861 2
441328350 649610356 1
342755870 748182836 1
365996820 724941886 2
498006896 592931810 2
192080098 898858608 1
836704590 254234116 2
293901229 797037477 2
399382485 691556221 1
645549906 445388800 1
289521868 801416838 1
667718653 423220053 1
942071535 148867171 2
998679960 92258746 2
343765476 747173230 2
285933222 805005484 1
509979055 580959651 2
689905094 401033612 2
531306186 559632520 2
532350826 558587880 2
863630268 227308438 1
822498791 268439915 1
677704337 413234369 2
681787482 409151224 1
122469139 968469567 2
899610577 191328129 1
499218189 591720517 1
188656252 902282454 2
500922019 590016687 2
830057708 260880998 2
224484431 866454275 2
398645816 692292890 2
312345669 778593037 1
596860143 494078563 2
829931194 261007512 2
141272111 949666595 1
906504158 184434548 1
840239738 250698968 2
141911513 949027193 2
936257864 154680842 1
562441774 528496932 1
246440824 844497882 2
787957693 302981013 2
118806552 972132154 1
922072640 168866066 1
652594135 438344571 1
539034588 551904118 1
929589079 161349627 2
646879685 444059021 1
145981209 944957497 1
921127796 169810910 2
175066311 915872395 2
548974706 541964000 2
950865632 140073074 1
641555981 449382725 1
483591657 607347049 1
594154688 496784018 2
400210690 690728016 1
944689455 146249251 2
983592930 107345776 1
229092390 861846316 2
150142569 940796137 1
961537517 129401189 2
393509163 697429543 1
309906055 781032651 2
896475935 194462771 1
496311494 594627212 1
357312522 733626184 1
888806470 202132236 2
318162116 772776590 1
893238704 197700002 2
503562036 587376670 2
416211516 674727190 2
991609247 99329459 1
281522896 809415810 1
730573891 360364815 2
773547780 317390926 1
211529432 879409274 2
228138703 862800003 2
242722698 848216008 1
894128250 196810456 1
467420451 623518255 2
991665136 99273570 1
97669982 993268724 2
698139389 392799317 1
921926945 169011761 2
168938621 922000085 1
350111432 740827274 2
925581542 165357164 1
169571798 921366908 2
569256801 521681905 1
226048563 864890143 1
301660291 789278415 2
923754088 167184618 2
963156153 127782553 2
420052432 670886274 2
440313974 650624732 2
628685229 462253477 1
732118465 358820241 2
407395226 683543480 2
623349671 467589035 1
406221824 684716882 2
893889705 197049001 2
369796183 721142523 2
724970132 365968574 1
905628414 185310292 1
234403473 856535233 1
587333897 503604809 1
770984138 319954568 2
221533050 869405656 2
344007089 746931617 1
333703534 757235172 2
263486915 827451791 2
199369014 891569692 2
961736542 129202164 1
273619996 817318710 1
109531051 981407655 1
452021266 638917440 2
447778459 643160247 2
640711794 450226912 1
482010600 608928106 1
139327300 951611406 2
215792125 875146581 2
527667363 563271343 2
108428903 982509803 1
352642649 738296057 2
966247416 124691290 1
673899444 417039262 1
703815887 387122819 1
481602652 609336054 1
726829640 364109066 1
166528908 924409798 2
321179600 769759106 2
655277569 435661137 2
889298416 201640290 1
359193391 731745315 1
270860925 820077781 1
186523993 904414713 1
570572708 520365998 1
888834439 202104267 1
346844644 744094062 1
876568861 214369845 2
560056638 530882068 1
332384361 758554345 1
415989160 674949546 2
356581807 734356899 2
371196809 719741897 1
745388422 345550284 1
195719377 895219329 1
651287768 439650938 1
350689454 740249252 1
341898786 749039920 2
570502781 520435925 2
394536565 696402141 1
272260828 818677878 2
279465488 811473218 2
279047961 811890745 2
358407453 732531253 2
159452028 931486678 2
829753462 261185244 2
813340515 277598191 2
705614101 385324605 2
668445545 422493161 2
144233011 946705695 2
776766287 314172419 1
246798749 844139957 2
545486845 545451861 2
186635975 904302731 2
811801624 279137082 2
671014770 419923936 1
553151210 537787496 2
755625311 335313395 2
568808783 522129923 2
700377096 390561610 2
359458867 731479839 1
184646799 906291907 2
326313231 764625475 2
186106885 904831821 2
534010823 556927883 1
413054255 677884451 2
304701299 786237407 2
129134903 961803803 2
514261552 576677154 2
264908004 826030702 2
940577980 150360726 1
440449066 650489640 1
362685820 728252886 1
988077322 102861384 1
903601482 187337224 2
487848901 603089805 2
351782198 739156508 1
385932136 705006570 1
230544090 860394616 1
494652036 596286670 2
961462324 129476382 2
796270143 294668563 2
263171740 827766966 2
605114791 485823915 2
583628208 507310498 1
303334611 787604095 2
316408177 774530529 2
883192817 207745889 1
564203154 526735552 1
388861490 702077216 2
434592963 656345743 2
505174918 585763788 2
154504642 936434064 1
679957793 410980913 1
734188466 356750240 1
746660963 344277743 2
553289583 537649123 2
189201691 901737015 1
123837622 967101084 2
951533251 139405455 1
830361304 260577402 2
674294525 416644181 2
405765313 685173393 1
397679720 693258986 1
993165064 97773642 2
743228652 347710054 2
126915218 964023488 1
145674644 945264062 1
199613408 891325298 1
118252419 972686287 2
149299385 941639321 2
963311806 127626900 1
222643839 868294867 1
424259417 666679289 2
247348596 843590110 1
972687432 118251274 1
196819860 894118846 1
648230389 442708317 1
729283425 361655281 2
418273774 672664932 1
112655037 978283669 1
521946013 568992693 2
970955434 119983272 2
681576169 409362537 2
685578810 405359896 2
142050433 948888273 1
889586418 201352288 1
100774473 990164233 2
277015046 813923660 2
510285846 580652860 2
907439623 183499083 1
683480817 407457889 1
229513799 861424907 2
586881815 504056891 2
806090811 284847895 1
501676859 589261847 2
305387467 785551239 2
293377688 797561018 1
677664680 413274026 2
794613117 296325589 1
417678653 673260053 2
205476944 885461762 2
746012951 344925755 1
267225724 823712982 2
713217657 377721049 2
506766004 584172702 1
248254654 842684052 1
903660022 187278684 1
289734059 801204647 2
693760967 397177739 2
347851078 743087628 2
407264202 683674504 2
763992422 326946284 1
342767956 748170750 2
317110665 773828041 1
827336637 263602069 2
880535964 210402742 2
221217662 869721044 1
105231478 985707228 2
385959807 704978899 1
691005203 399933503 1
814961231 275977475 2
99972896 990965810 2
915921497 175017209 1
400270648 690668058 1
432207832 658730874 2
538285516 552653190 2
394725975 696212731 1
682256008 408682698 2
564705487 526233219 2
828194619 262744087 2
215113262 875825444 2
406820879 684117827 2
263020164 827918542 2
322022740 768915966 2
611457662 479481044 2
704978940 385959766 2
656245216 434693490 1
371887378 719051328 2
419896685 671042021 1
844634636 246304070 2
297951032 792987674 2
219995460 870943246 1
311630112 779308594 2
581067507 509871199 1
357053735 733884971 2
198215829 892722877 2
948638056 142300650 2
162957055 927981651 1
568608921 522329785 1
363290019 727648687 1
613843983 477094723 2
321045733 769892973 1
947448235 143490471 1
918264513 172674193 2
795563057 295375649 1
366286732 724651974 2
208951720 881986986 1
275729741 815208965 2
776730594 314208112 2
117704683 973234023 2
663160220 427778486 2
230232754 860705952 1
192155350 898783356 1
105769047 985169659 2
791523382 299415324 2
377215277 713723429 1
408044383 682894323 1
829455604 261483102 2
758025705 332913001 1
256234868 834703838 2
746697074 344241632 1
465195673 625743033 1
697091061 393847645 1
585892851 505045855 1
198878600 892060106 2
893891078 197047628 2
240320294 850618412 1
259607676 831331030 1
159720104 931218602 1
613415005 477523701 1
234621578 856317128 1
875421580 215517126 1
384087158 706851548 2
862428453 228510253 2
898960307 191978399 1
97078689 993860017 2
145754645 945184061 1
584713304 506225402 1
507154843 583783863 2
290707906 800230800 1
304690200 786248506 1
367462038 723476668 1
107562856 983375850 1
132641229 958297477 2
812996398 277942308 1
281726812 809211894 1
287941184 802997522 1
94172537 996766169 1
777038261 313900445 2
355197594 735741112 1
928669048 162269658 1
152079284 938859422 2
175489209 915449497 1
624752913 466185793 1
852884974 238053732 2
917939500 172999206 2
370596835 720341871 1
575298289 515640417 1
964408382 126530324 1
301424624 789514082 1
751315437 339623269 1
387119251 703819455 1
401991261 688947445 2
116547882 974390824 1
495974696 594964010 1
176337796 914600910 1
539333110 551605596 1
914816072 176122634 2
109036776 981901930 2
685319492 405619214 2
237152073 853786633 2
173980096 916958610 1
370787339 720151367 2
357012976 733925730 2
677257645 413681061 2
258287797 832650909 2
349530167 741408539 1
412553159 678385547 2
468463564 622475142 1
683175875 407762831 1
386355828 704582878 2
823289800 267648906 1
161857358 929081348 2
294877516 796061190 2
396894110 694044596 2
102821728 988116978 1
586538034 504400672 1
425256259 665682447 1
664193673 426745033 2
962150910 128787796 2
129121895 961816811 1
490181743 600756963 1
129265366 961673340 2
331871235 759067471 2
105923190 985015516 2
624041447 466897259 2
552775812 538162894 2
661801908 429136798 1
403557200 687381506 2
357925203 733013503 2
431689213 659249493 2
724028377 366910329 1
200571290 890367416 1
202354311 888584395 2
983575551 107363155 1
342018060 748920646 2
950253747 140684959 2
362603930 728334776 2
190182009 900756697 1
183904207 907034499 1
450764173 640174533 1
764096458 326842248 2
94509528 996429178 2
711647327 379291379 2
567748726 523189980 2
260012295 830926411 1
364308672 726630034 1
483305054 607633652 1
743590362 347348344 2
489061490 601877216 1
576348796 514589910 1
653837555 437101151 1
439328571 651610135 2
157165453 933773253 1
94436845 996501861 1
426726717 664211989 1
758785216 332153490 2
725640128 365298578 2
199889197 891049509 2
472772992 618165714 1
687309706 403629000 2
842368375 248570331 1
126809054 964129652 1
693369761 397568945 1
962849974 128088732 1
937706623 153232083 1
446176788 644761918 2
771373553 319565153 2
198558969 892379737 2
753476809 337461897 2
137181640 953757066 1
153135273 937803433 2
782128147 308810559 2
806739768 284198938 1
636617995 454320711 2
295458695 795480011 1
463584423 627354283 2
113219205 977719501 1
319328283 771610423 2
96581655 994357051 1
258034207 832904499 1
375708827 715229879 2
759006275 331932431 2
142680932 948257774 2
380159371 710779335 2
170275762 920662944 2
222085786 868852920 1
402428096 688510610 1
158931226 932007480 1
573802827 517135879 1
237911025 853027681 2
181991395 908947311 2
136510812 954427894 1
107895373 983043333 1
964760634 126178072 2
756807009 334131697 2
724142448 366796258 2
94419401 996519305 1
149795334 941143372 2
360719055 730219651 2
394746250 696192456 2
473526329 617412377 2
277033561 813905145 2
978990897 111947809 2
438632029 652306677 2
995962087 94976619 2
961131617 129807089 2
418958247 671980459 2
333403085 757535621 1
132325686 958613020 2
570785850 520152856 1
593305243 497633463 1
290008051 800930655 2
849265538 241673168 2
370931329 720007377 1
511148428 579790278 2
912901080 178037626 2