1000000000 1000
468767146 37327333
719630541 46012685
145455765 364893321
64840301 132379057
474139436 302488490
827023039 30551657
250557561 66091313
960832645 61523281
437278177 288079418
737084281 233786536
189548911 142733987
364194812 25501633
138631447 34660380
521663956 394019949
12676597 19655065
33284481 321727681
173098837 173293781
474428 713752341
197264061 331297826
283529064 390880309
437448542 113575873
320931370 470166517
112010026 163062505
73799911 256423051
89538220 916481251
318051553 728163
175946730 193595647
135660188 415095631
787109566 414473489
231736609 609151508
430722991 560908027
82553794 20325410
361198918 445493127
197430517 617187976
165886741 30181135
79999255 103607633
282699601 130415832
29767266 33634637
773216207 34559111
439990901 177459259
387455734 8110162
696187407 496622809
67348921 2523549
41824182 25263151
10668241 10897061
702854785 49222141
24912381 683178547
242295725 280609265
126899709 271733509
107541049 268179472
134285869 368381409
304899316 434737273
12898129 822530934
110075096 60542965
578763894 187806736
27338035 541203157
877907969 191399893
315399553 795274681
97761441 808504396
220676665 58329832
17436329 371675081
579192258 166231297
633392104 712529143
227082875 176374990
288920751 153758584
6144400 270380751
101885440 430411255
522476227 555579109
370142945 167032177
63148019 89823618
158574283 439932685
116059495 289340218
140982139 111280003
264127956 77811427
366704917 180621019
76100727 72253372
205816556 531516763
4371823 686290697
449574039 31119323
77702316 388731535
32498896 55698819
278010876 35069989
277964111 493783681
309167643 259873505
20475843 117118435
309688141 445826863
241059225 60773749
63351197 24782745
334591121 339392241
138715669 39667219
8899649 35412040
723601537 901379161
15021964 219356236
323947729 269737609
750144541 72563442
45391825 126853551
923799801 660522269
5867026 230527874
266340192 371618471
150396025 106046695
128114306 344725187
470904513 493437686
329196161 23598807
60956053 294623281
200426805 249026406
183799979 614356423
4392721 101121897
146651085 430510150
402178866 158531204
59679335 808653965
145225881 345846127
6447273 136286376
21296082 672532536
145029143 747379231
266110273 481217521
42204457 24742241
529192877 268930954
21966211 179109329
472563913 327866670
37654371 667156624
49974601 42274123
316861729 444358327
17179212 513909319
759284801 85168161
26776639 277201637
627435611 674657685
33940481 131381881
410843728 174003313
173401231 753889886
669286417 442736561
232638730 389096314
125004081 169990607
22169336 199076111
695000241 4794195
27949501 1590436
273015453 186369590
90402404 19395733
599873187 240096435
478131136 44609846
341923429 60026539
118083421 343336358
88120441 81556393
413431978 461909681
30368487 101770426
32762465 25711933
672556228 962882121
458051269 485204889
2862839 341607817
125386939 74888381
158885256 102077113
211278112 79418407
31246881 462425425
34289641 92301903
171109813 433988365
1651426 12802945
119931995 334186147
82731723 769143915
549387553 55890217
444380626 773096017
591395405 27788804
79979105 144278049
641994497 339144125
112133575 582939682
56549382 92695571
54703397 855407281
855725 246502585
280245088 214560877
698054601 829326651
437303439 354254402
170574337 464899844
21574161 384009011
519822577 915320071
533392121 202501885
335572147 786893617
325909376 664560919
877510213 103243951
301302523 321046731
458524715 251876101
298442481 258324958
725953141 318043001
446386801 17809357
133112721 137237101
342277951 321000161
92110801 273235425
131224741 14517361
755992201 56668987
7241185 428605666
149124637 484349761
792699076 516498466
3961945 778653039
259428701 170657004
8082813 346796737
72854968 278242777
105569361 434877964
197431313 133331094
55687564 50449959
106502665 322608601
580917629 254076340
10762467 128206035
92065031 421246911
82157901 246549011
23850911 7485825
500672152 6073497
545158161 666490441
127786225 54567436
369985281 14441417
83213121 8123937
267474945 315922881
20550139 490905325
90934813 242552161
141783851 212146156
773202626 771001309
40938871 192823313
96645574 15477651
53211253 149672105
4075723 508372537
4999703 8686657
371919961 24631622
583551431 305199559
386982341 384885820
20038481 157578531
178618761 461831410
196230766 56267002
149285448 428707981
267483901 31359901
884444887 92097671
226581417 353970783
170941475 790476413
177009346 496062049
26661447 328094723
325924534 84645001
926848225 586078908
168278221 707979126
622687599 69229881
232877225 59793925
60601793 216033793
56725599 44432209
47823524 345830689
58663993 118261564
20439693 186447210
173979751 295311265
384266755 108742620
480416084 14945131
283853857 219135585
87198751 245539641
274951 327163591
20414317 292311831
633266117 560282821
14600833 19436045
325507817 164712861
406318265 60450097
36190604 107153665
794032994 338916679
171328840 386456937
30846553 521927017
38031841 78150781
663865441 493084209
84504577 719443231
297999693 618096331
339229531 569395077
97917107 236196056
23713516 380875641
111024131 31373551
137911141 509288389
88398155 25530493
450332025 61698386
334882921 357866521
12124145 8736251
25120250 369928757
376596074 1580149
502066617 66916081
394865591 137778424
532837761 369327247
80575957 430484607
227664361 76807131
547176673 124329325
173435623 19078857
204830253 145314877
422638573 5130170
327891411 433223332
780689681 966962657
26661363 52369066
237278031 26181665
76581521 689411137
23765147 112930313
272570068 534150181
16985 905821541
799866434 83510701
410844443 234572629
138314939 125688165
25078547 282242025
349819211 37042093
65933801 720063769
59385775 525491812
314354481 354236786
348169869 276277717
194038759 248134699
671116735 316188016
378471081 346427281
618720885 529424905
438625045 325400185
47397679 111196627
201612247 364910752
634475991 853491101
53806631 132289781
327808757 91080799
385828279 71081047
637533001 269686275
217665301 146505939
12987649 173106650
367982831 58939297
101170791 141256809
218075881 19638151
45261508 151416871
545455807 7406731
141552783 196086868
343426821 236856311
83818288 161398227
362407393 13448661
317136073 14402305
843237697 139410932
229069775 301976821
472206729 536606405
131103305 82817028
663100661 32477926
68444253 26904905
40608389 33717755
205660759 26139985
49000577 110957619
5702727 290628876
409457091 147850306
467746813 35610439
139626400 50086210
446895667 792105615
308204055 190496385
251078224 228793622
38619757 397166977
144529537 147717037
286400001 37489843
1872193 901933481
817737691 73035271
166103860 27407809
189273175 102369595
879388497 159797333
318951309 59907719
321141473 277648377
339258589 26056178
44836426 182753065
140581501 28488841
187466651 615885557
930659953 492239707
660721097 19954089
200077921 7978781
264932837 688996071
145583317 234910137
138624263 2200365
202818925 490777240
123053686 9006181
139227592 476385319
388219997 10150567
69900841 187971081
759351418 25116646
130173377 250816151
33751961 202654870
34485793 57962785
324302941 440080663
195269041 119028101
25035595 314485417
721135887 32843476
50789341 74904481
61043729 735178753
181190251 304252481
519944671 613509645
290373177 3477265
5502756 445869881
179163327 561581253
5644701 476230183
234503690 578435051
385646619 228225061
538716602 712509227
71459713 89498569
83860816 501238599
420179529 501276139
132860332 185405568
12823693 429121303
30486253 30766281
813775114 300387601
884799488 138313993
145124101 5511241
883994881 75256070
143381843 87309825
91921501 113067009
226367911 8117621
194938291 23827321
692682281 628859899
53360966 201876901
104164147 460542427
356837069 99963829
638841113 836320201
278823249 33649813
8842695 580361797
94315331 58617413
36751159 193691841
706068663 973053921
425192296 184523613
233757399 110277701
531778201 444348033
59433277 80305758
127679905 155822443
409494385 40030615
235464585 188810301
288038899 610614906
301942681 465176874
906344087 494917477
871612523 54919081
279428801 239580881
126680581 234453571
530513705 385248641
658853521 61731583
68253697 228701182
509733263 19009209
57536501 758342274
117825586 93547001
19000257 14694985
1205326 26038105
90408509 729925985
299638721 79226109
399742659 387355256
81150182 252445441
813240226 690239238
494841201 491492937
6995267 143253117
94967926 265805857
449769511 75012904
10607851 582414988
228727342 311637662
57068056 243953669
50539777 532794927
88547809 151670146
619966901 606472044
10316145 788667157
376368957 103314108
62588629 146607864
11260161 146179675
342953551 180720765
201456951 13500265
71595382 402044053
114603775 241063751
71290549 125866601
390641329 357132005
830376769 552433919
948969785 644147824
73810171 23386371
39194449 66112705
13616719 274923705
49326551 308709053
591264801 544665699
56521297 12119251
171921947 31938859
487261351 312669343
97740997 445247065
718293304 359280839
622096379 354993151
32946681 549635065
8268265 39320479
268148649 819960709
87428030 215900206
661262365 93777733
22778964 280124867
143124113 613647836
135865446 389760889
225834351 891350301
141480337 427791781
142054941 755986588
440163915 292685740
97254501 682610688
376417258 874216387
2683751 124785387
121005249 238688185
63045748 207562565
502220804 211895705
150563449 5474642
82930862 51382651
479520067 639376577
180108631 334279251
89639745 259607809
253451595 132508481
121110537 18889417
25823151 123316657
408919169 400730253
77507501 34774561
5790981 399876773
61349977 20514445
732783685 13867066
378861484 94776481
532923587 114162685
676162081 4520881
252500032 77198755
231733537 104515027
18102761 648668666
226973056 55353455
84748533 240640159
6912583 119295609
782836241 645954838
521821081 366724953
19908616 42175232
337179349 28180261
538202209 61246719
461119681 561653825
353168497 282994945
634841362 127352186
109506385 143790914
235384993 42713347
717102361 624569487
361266937 137313
154097137 184119121
213720783 296063641
254204149 60192276
116703197 20319401
10326277 2291381
112014208 16616701
614669901 45948185
146193401 338232142
164209168 86636489
6405811 43777543
545960801 78625985
111481741 4771945
795950357 359013205
307106683 193224646
668281009 53547
350438961 266077576
909042324 150144741
62349376 168406576
99756541 106220451
560110391 302968249
279353247 115554881
486835777 50079277
274541515 146368685
2574268 193256981
63516448 283963901
49280572 604044596
52367026 487421817
11826829 132263668
298262762 644988301
723814501 101919406
100491950 139529057
138332704 99496861
122724361 39639678
313475501 750590821
398583501 188372539
447298216 547808737
100584037 754981073
625047721 24535809
216150811 288172043
540519093 259053055
51113982 27749689
59567377 82639393
871918594 387295174
399514753 323266961
343680361 543157945
11044929 178456601
39149740 2710345
512187897 278217777
52774456 466298806
773922979 26630149
554824353 117198691
199174281 112741591
483264635 13733981
41260721 626366427
459842974 369729513
819162549 714347026
362091871 13931575
76932451 380833909
241242301 120383542
368121741 25183529
82698431 419992365
65396641 88047576
652056529 151263736
197706051 159782933
321042361 51008164
227839041 33885267
99942697 165281799
178764166 616851623
210861575 62360971
355152799 571551523
8298793 106095166
58506022 22058601
647379757 38098801
659236697 235447073
38757769 171100117
313144883 454604909
13015900 96567281
573032073 79169959
247175041 60716097
259439125 630730553
273158712 281777585
217349500 142323088
12294295 190050673
51390073 100906678
2515301 547481467
111023431 255826395
246339899 352515781
878922145 592099369
286981101 694797073
99140837 332192433
177781606 61985224
426022072 88359549
38442601 172873468
408783791 127723024
111953693 125809249
19560029 161735031
748438111 655978525
184322496 107965089
46630273 56330688
356378606 141898609
20412901 774218251
27411937 171267353
382498003 87940576
16427529 199906421
61498031 142410958
170863129 19191041
183300065 284000277
2108871 273315745
37816021 709710235
65743327 46422613
22361197 358527943
536433859 409074069
333119431 324709042
470466361 255384741
669323062 409741701
770422403 22945197
397603195 857525101
401234401 61499747
102252453 237188797
72938722 264238521
104756653 59874013
621360264 859069758
293035509 356235069
316690936 453147351
30027376 480455661
137009826 462347481
70813704 2530369
575950777 3060177
23510841 216766273
296415274 9982106
141147256 201278857
158279380 212506067
42894045 792106886
27228597 218916424
241157857 181217869
4422098 202194001
408156421 422709721
275400308 305755401
309007345 678848281
331685341 1478017
129111651 66120121
86430425 19708417
246209825 99902551
600366055 70772647
284990833 2935417
537861176 56527075
14213025 187968083
74259297 989631648
31363641 564245579
19998721 120761191
499659526 438507649
9753976 382199633
223693413 220622506
57891721 6558841
27963250 402074401
75697376 546445899
293824477 61472951
148764694 635149329
56667110 262349713
629626233 120470824
83511366 63152230
169142849 917704880
73705698 169827793
59327313 851802589
891462521 294646129
554881941 538383785
121318486 446880017
155885578 336047529
60814495 210670041
246454639 45382130
99218599 627083821
161382245 53461377
221814057 5408341
207066677 354848299
51533341 215184229
80212609 227734291
393426177 53616046
6195123 649508126
355164892 77997851
495485101 274315829
92852089 549527425
557580301 212931737
611083036 457318601
123061761 44312269
641871700 65935642
297298894 169036231
32068075 20936574
353717004 262045995
49788073 103896999
147492638 91188721
208714861 67946775
57762181 542032251
158731920 9535456
427263717 28228201
25728730 62744842
271404819 280768499
197367655 73184530
190514105 144862576
80912437 779189302
76661374 35310906
35169127 69977821
140115301 783807229
49635279 198508580
424711 78431627
10727641 48577313
325156651 101723473
72243865 394422701
39820301 385255061
69804658 418534381
367429601 4892357
94498741 419648633
447603949 352083333
127438707 72399962
82444573 42207361
71660476 159284341
770424249 184362226
243153439 367960117
334952141 554719561
8494909 328537945
202623415 276261895
461504968 486773701
143593210 292744369
878872501 7313508
463624145 126333476
819435565 234384897
855793940 143569635
189903501 124426454
235673088 183102982
16564721 529391991
127643257 18019905
83316953 356516261
869343918 9682075
308034826 94824881
338343733 633092071
239171091 595637273
160862293 116835601
90048353 130739061
450172351 80192085
967155618 161754697
878520826 33043868
700867531 92811082
515353873 52500659
155866501 261745206
744814528 240426190
733559485 2468104
450246193 490545784
445943002 103130161
71039098 600597505
521206064 70227193
30604681 583342215
130277501 193109317
40755261 54303661
127291561 91879137
78053529 513387577
197887299 403477713
530833928 117232881
525276849 248516377
52938730 371178931
330366961 44449171
435162554 403131376
19536229 602809777
66170413 83423344
559301544 159212596
23411466 149310307
171347417 714731304
163592001 58180501
141479469 560078332
49294565 412763401
70165147 642711457
201230377 194879062
612782038 256036789
3334591 213229930
18669313 71341201
463431081 573821551
386893243 355923001
3261961 138353951
173728843 129857608
118441129 78373890
491186097 29820901
45199245 399470387
16271817 31289953
596520961 593573401
74565857 437558983
161193418 121113726
817706170 288227815
289619793 182372926
859745251 39736495
18661041 533615392
6071329 208804726
608911871 153035326
194775337 176482945
482609503 890438221
303183357 153028976
867012046 129172561
516079741 27955978
413956557 62260285
251522001 732227111
408678131 39535276
574496928 66006348
255332536 2943253
340627811 291603188
6289461 270365404
19874566 34860283
71768076 53751601
343223361 456756742
430269491 574751
55188122 197770951
437602971 182813689
91287919 51745450
28449929 99593929
928352737 239277145
96059215 97292140
291983913 36257761
219819073 317392141
936315577 71176673
27885125 4678873
6204253 142373484
162480796 611144689
460715071 619548946
39938302 467910433
2742163 142378852
213550621 396350785
152369723 685732252
450341336 143640741
939084919 259857151
669767829 2509480
143249783 215857705
393614134 151864747
445061511 104464387
685119947 15391239
914335377 245903164
49647233 282402352
529841872 333795830
41879916 212346560
366935409 219732981
21032597 151798949
259065001 277598305
12221581 422132569
70650589 161424361
313955190 70330969
597410265 571583993
642173601 373275701
593028130 688729519
58615971 338518360
299899626 413236531
77815537 693135326
604618561 21066301
255819862 345429601
405672625 41012193
7173433 388803835
353254161 458180170
678178591 23832697
664628481 102837037
122746051 240711041
217508677 926016757
537234051 62167391
75548205 698636233
64590465 53807401
435810813 549301501
326989277 112609945
417891471 137915317
286726125 28649550
55183051 45049888
84113137 83787341
161374791 251238523
256735471 318815055
25916610 96212221
342971601 281486008
12066749 26011714
346271306 81652453
39725892 83725437
318634746 410244651
185030551 611965855
67734010 106743148
165304989 139376745
353525723 356735515
632599962 205317256
88269763 638356821
235927833 196228976
399062431 239379676
541523356 552665311
456976696 839640771
86489882 89541381
13790073 108887282
321706332 123071257
412136985 34333597
164171287 42677041
202600927 614682649
198728221 361687063
135247204 490279768
151626483 121016377
988972194 132582086
111400174 858781345
164732129 496452312
43437801 650886116
296196682 63271752
829084957 20429447
189729581 56146981
43025419 562835155
122324481 602489889
45637541 571120001
40599409 432988491
449977951 71168392
655636145 48586991
304676629 101621577
395489 455060306
222718396 391245671
50163853 10888561
5688625 832387330
74427526 456904513
6662387 18489686
172853473 73359438
624527009 224169919
773184577 497458261
703598611 898978161
68259458 188011941
182208853 152362862
319096486 9689113
289432369 705477228
986741680 653159914
29007601 160845247
639291940 21980971
332865133 346346349
82644761 7311227
386244101 99594751
33343444 235836115
215452833 573392503
103214707 32440657
392187127 306253326
4684849 62188665
89510135 81695161
194182851 21867966
74076526 246213694
139307662 290262001
64530423 372817402
76519249 284896660
23033629 154436261
24213508 3579529
26975199 350585665
24377896 148909354
257679841 495780226
577596033 102077701
752738839 13517309
180250759 44993785
410360699 237179566
54083205 150827226
800942417 75133548
110798961 698693150
115357201 612301936
15749316 335825942
690890896 288174569
819689222 406357673
429117879 34795677
289984553 67804576
333496177 530511507
486493569 4592713
178172881 38258661
108985721 769666041
77405841 675289585
7830791 103571064
388884385 8867833
174517201 671885757
615773201 59608801
359632039 103739920
33811521 569978401
182226721 31893181
605565760 64693891
158347164 454107816
611719383 83144641
160991047 14567281
9021979 454447357
108261566 8146147
947346547 214373611
67425684 2452324
61842999 109535625
437965417 577489757
48789316 193629871
560749211 442355241
196956203 86256595
339560856 788532537
354608481 2996833
113764449 230066397
260732281 200274049
91454825 177464129
198873793 2661753