999999999 1000
289790171 191313877
12837383 264391189
145143265 171221093
455814577 607693504
110925883 125233578
279687079 652516831
209409201 106062716
299356123 17315039
895129943 70388155
383168941 7464381
54759889 578355935
153764678 403861589
382046707 305476816
604003891 123116989
237615580 446407123
115704928 155771526
279930288 15105917
528259089 7614001
898573839 400945135
672960502 152188310
286534327 527120826
139004065 650765105
693156726 194710816
462525537 989278774
16317289 5794189
101613406 434172941
13422073 145869005
602843473 191916371
202485239 783910519
227412741 705902188
736120979 236249197
380745159 1430857
104866960 59023371
41235913 504009537
648252276 722633933
344265051 84090239
34303853 406188841
611088841 225691786
378738609 152891333
118817659 747762799
568150336 700228040
50258274 21960221
307815650 6633879
7917659 231598934
158390192 135889637
37328677 135853012
375178301 146884771
12139963 683006323
127333825 636766401
263004232 192769187
2832721 514102681
47463981 98364976
266548356 486383757
754110601 924639249
567063014 46414512
90271943 18844129
510263875 352205575
7578481 2411536
416747365 33382117
356410243 755370
297296281 821125831
527497467 353860861
22479001 160780741
169769546 60878164
104052532 310843303
31852542 350947455
490268710 189150679
73316751 212117732
500586327 119995033
588235521 6327105
204994261 13601065
60501783 522934181
154395241 295459606
271285219 91962957
327426956 104291403
151631253 134399161
425982584 72960669
83305333 45493150
99797061 538360251
582987861 634665445
332128557 568999121
392216113 598379079
337873146 116379667
17091317 102917549
364606301 449052961
330041782 879291073
561130522 179719973
18102145 520060684
345413353 15242657
9539245 300605595
417491317 135068413
307101037 196939297
636777154 151175615
406441145 409998653
227842128 171844609
5321667 207015951
56259130 710342125
165962545 494611489
763992086 757600529
103158991 358702861
42819440 84892402
190614571 238629907
18735985 583207529
86274849 149800393
330204876 1373121
596938222 299047404
190043331 253456377
224633718 710317195
308349835 174904681
58431529 266327297
38393113 623717401
50379556 155982682
592568225 344349461
129852757 319028791
84809051 33392634
31093227 172708341
158615711 120954961
175191760 76268781
17833743 397101056
354616505 121110439
80778853 150043045
374908296 233760685
147869051 294362871
201653885 120965209
476149676 468732449
2494309 157410261
406184707 411758829
518427951 228455661
487615849 112370366
357885001 246653653
6159536 331396393
309368641 66578189
270902465 28323871
512649321 339498127
413729711 342561007
520224089 469086151
75842271 219614721
41286349 376931335
297929769 18693325
660914121 84478433
58984225 300243925
28701576 137445451
205581601 136736065
116131241 507542745
191939857 36910231
200260185 108311251
543891721 9738855
98882911 374581711
121767505 67606165
874409549 316381171
18110158 91621881
582948993 334754547
166931953 25820289
37174086 367464981
381060526 266927016
308183953 825994369
264579497 213760987
105332505 145098631
43337042 52731277
266890651 32121053
147753841 214172509
90781048 46300531
372127063 279337002
92117169 79977311
557968411 893059219
270569137 3531583
13102151 267906801
105554854 724305497
20948280 119540156
18518971 511476578
745355803 292402721
124899041 453236221
280588946 214413083
595553193 161556751
452426401 167962451
16532797 49020017
493144666 680699801
336562953 18955313
359063841 189663427
8650280 183448585
1542633 60593050
106006777 749735365
135886171 467938525
11087983 658048161
444287386 243584363
186213301 909078353
64766641 136711197
285205411 4143451
904558021 46594373
166601797 281304748
686200539 603624487
153370141 385630273
192246529 20501589
55001701 738572311
307842445 261143104
40200891 131128501
7596561 694159075
130540411 621198740
710314111 199823631
68129244 129960949
129883313 610299014
499683091 547372913
215292666 454582909
287353081 9339760
160642861 519156253
517080569 213987201
36100709 25637161
9802398 320176128
109360201 6276384
384605857 22543441
301997351 68643653
196628131 414050473
145900945 129445937
601194421 14483041
46005481 293431350
117439441 150131914
482989120 218897441
512285749 280929251
281314241 140098076
65868001 320190321
277341047 488921941
63938337 178827113
248813753 917977672
41592951 69554629
30301363 10451377
183146117 100036071
305214716 614500984
117336629 12720566
550115193 115063039
304842377 259051696
225182251 9311605
411155101 578731481
32061876 8147686
362017335 76250001
115924321 191939479
2607167 744210018
379822801 262880136
48232306 45789129
106844991 96521190
25487001 29563249
9861025 598362657
415675495 33991412
142126815 82864189
35668841 137608099
17875201 227033899
231575731 276222594
763183987 464542625
537510601 4864501
392199461 455798997
208410447 176787439
349905903 128503945
636161669 705577461
395565193 190688797
38781870 573021245
381737721 556991191
171354121 896425641
14976298 87629477
510837911 612011557
393425114 17657767
396468136 210622413
744758554 71759681
1720723 400240569
119744941 799692961
468310753 339021762
272112673 342160216
451050568 128054716
316629829 412499539
859084801 134538362
698630401 15079102
3639970 877807666
283738001 723519217
447099116 33046915
572281813 61041
47075965 572967474
19803141 206553257
332901889 534119641
252437200 285497860
232373153 272956364
139483849 233124423
269597377 527393704
619821977 239866301
59746687 664990663
23309849 22919056
246415009 157241192
70105246 517940827
117570553 365073702
622056805 167613751
829161433 156362401
161955075 329957226
452256601 549170983
20403098 878190977
124337011 217082386
212665846 104798422
687629710 449726881
594370037 247227806
747619566 423080751
40475216 30703597
682763015 112376881
578858219 612106947
132766429 615306025
41304149 59502001
109175991 53166713
67480159 33932557
170752505 424521851
13942189 97796449
270687565 234257041
75289677 11931805
315416141 693921819
127301749 169590776
492682746 472614499
573237351 380780929
450862983 804900601
41793274 457462963
462102031 2260156
610194621 190530601
70519821 116963817
43655332 77358051
14165007 288517450
265522038 8424246
162522490 83977777
983338712 540174349
96888643 83759551
27366620 94201761
365388075 119284581
373371103 226723771
432019351 376058311
48928174 90405756
338118744 164412811
132486943 203427057
790808864 815530255
246447105 312276007
62737543 130846163
160872705 662846273
54398641 799896871
149445121 84970621
331496001 8403439
18049663 214207246
111334402 20636421
511971751 519608449
320869671 8371495
794968087 308447047
242596405 248542129
139161985 224980721
277693313 504958411
306556596 12880561
4054807 592712738
20952936 194396308
4405402 579053263
330898025 174071876
87516241 143183323
660094399 776245891
132718261 616533835
475561333 80118921
21878939 123949411
61187501 125290777
72987901 44472334
322802281 163436716
422365770 311046321
136663255 146558127
50600449 160785376
333536764 137485406
657798021 452778096
349727158 254808301
144639157 46614465
474692155 789399811
126610071 120278145
69180851 133685732
13402360 163440916
160326065 100693058
538840457 39950576
812675700 896118026
909750529 553940905
709503356 517027761
13867241 389972161
188131500 82882865
575225673 136625481
445997633 266790288
1646434 43298981
94712601 393571705
91062898 352284454
188211703 58221721
113789287 489226753
203784307 8914221
637965565 53011433
127826269 213432008
345427962 42658646
284704597 272226367
292053466 282319451
100155931 387713371
277508821 188942086
509439311 350722555
226343961 482735249
118698241 86656476
253227856 551329913
15121408 56908465
16623780 94810096
16291282 174668187
68816805 66532707
1490366 140116534
228136777 759873
312607945 137852992
13933081 383223842
395416981 186585301
263658353 546223712
221200261 158528338
405254389 15084161
13882905 220476361
39593 746313286
110360873 564763001
120918876 649627481
22478684 40768664
192961189 208869221
552604745 120921216
16873569 208913951
156248191 104961601
406005601 630409132
6098054 75747683
263205451 37358507
644288503 173286409
74708368 862231818
662138881 396294969
73794694 146083501
268215741 21959801
190998046 727925521
811529161 12492481
74293649 349530343
30257857 534986301
178408538 30051001
238539713 144707507
492120897 55701331
729700656 54004826
259752079 23693911
233306074 733739773
210208469 318495449
665166883 86911345
63573713 44761681
261556901 883325167
69911821 127444591
31539024 80020786
706719631 485986369
141477337 268814464
798932993 475857991
346516619 86996313
80120459 183572643
28552419 796084209
49782426 424276537
608878225 46291376
101662401 170473465
548981081 57182434
713716865 185844010
480601206 28656236
168188632 102274811
62870512 113792417
2436605 591382969
24764887 353450994
3894492 811028481
88580407 74900651
217568781 180003166
751933189 17300361
107210789 462539473
699459001 319086016
797612333 4418523
769204684 11272676
392060766 186711433
22855456 140049251
512840416 214131137
108482858 42243244
283497625 111827071
60815837 252587265
611728307 406050599
275172817 164116625
349179517 936661972
853864033 43232615
242389153 23431233
493127047 259450348
92644644 223465449
70739593 70173181
23946471 254790028
436159822 779433331
224196701 54601561
547765121 177322531
79921576 18430959
149412061 343570388
844414246 145838391
174298081 158577370
409329943 313633417
678561761 285790083
8301165 100781699
76555161 15068431
438131953 427929781
761581465 697568699
279279157 495947017
156939236 332128889
87930931 3537425
598069969 32977057
597120481 904623213
340005849 161379864
601178740 236354548
26392501 358131457
55417501 296067611
464993211 28472057
171662121 616940947
479052068 456953861
583176889 385957767
576997911 339753448
421320538 98366677
256683826 98072457
419523833 451608977
786355012 441505879
22633501 60630681
543132101 89338715
664588651 201714529
16075354 91443569
112078729 111273358
4395176 206546257
284677225 17938055
903490981 207215035
91544500 467129257
333145261 108477245
10643001 116920301
138780897 212754049
62186939 113826208
119273701 268112679
356766787 128692401
709125488 9154315
823688524 555399181
537905551 536782681
102078432 389611732
21375031 844102671
235519246 381746938
660546819 958261003
689056358 213782135
298163561 21076791
659844130 172208001
624080909 21522658
500602133 80853543
280251 885089587
31995160 226216383
217148581 592927168
937859340 303486625
933898001 460899821
383429881 143577617
557759593 508290939
640440808 94862895
774754961 374427577
86973121 247457535
260157181 373219919
843617653 6165273
75266115 291286841
186789765 245608129
383980443 29573761
3489014 111294145
54890533 34189071
14239201 320661511
261512963 5911887
233005540 90336273
91295559 55612237
267252166 231893455
907250401 330780001
735529887 487059870
166457101 70480726
61172203 159113901
62402769 541309663
213616105 10344659
226819261 108859234
35365804 371553446
188776632 234663251
893394951 15144977
15614491 297227837
512043356 121602581
235874326 233145001
457083217 663219445
424865429 343558678
192295141 857525101
688948143 10207233
122054226 214454458
84495321 34344433
3396485 616509634
646403401 156276737
672266001 649310095
9364225 118487791
110422376 386495011
461694617 244513969
332826792 114736315
30812671 473094773
561958557 91589121
354684669 657625315
10534691 172624385
293823141 207748431
30512254 928568411
347658 336115066
339507091 2417617
229535217 347290327
84867757 160267775
21415249 64115089
85703859 77869149
1951444 636892495
196940161 778450112
262555463 431665256
5029921 11367706
188084755 519258259
199909034 42835002
165446887 37160996
117193825 34411772
450451109 35728798
577105516 168433265
379955941 82225567
195421519 1392630
62806412 435703070
87777753 970436565
326653005 101478281
39577780 734747617
406750561 422176141
266116692 485631278
196023125 172381026
131713185 32819951
217285597 9718301
780009265 60045717
72293736 51617217
13083006 231888251
25885774 52237225
751321231 310464701
43242689 577604377
371916532 110008165
62467915 410592433
581305886 437689009
99020517 42685634
19716680 2334769
112593299 56202817
131395881 15991013
19036540 385574716
443392921 1995781
221498509 83327851
112426737 297477151
136486747 235313209
659832097 314969775
406266561 91475690
873072646 928320944
83249409 191121351
186884275 333506161
582133553 514525445
22136179 457744870
263085226 60046141
288330813 544974265
450299305 668331913
17079436 400543781
258831656 331623793
340822401 360105994
420850 46855426
13378751 16549911
760139339 99227381
652255913 54409951
726470047 259472257
64787273 278486751
453068383 468434579
70377425 229920643
21096906 6801601
335311435 468955651
262503937 384421227
235705036 58714561
220990051 2277712
96935651 92591925
138344581 643012243
349189681 169172896
259780481 222079126
163106389 147306483
242512147 8256520
143164243 69975199
720048161 181786738
89935235 216827361
466457144 900498856
34188969 13602
397492278 267139731
165968305 179948317
661058995 192106783
32305945 224798169
127806499 43748225
254425348 291348946
217291170 52739363
898649398 46690365
692816401 223776129
315478945 389393009
156434443 639197881
139447421 543494326
50968905 244916876
82060 226667301
105539599 105812673
32807881 21686641
268619177 32801671
48694316 360168355
88847611 301587079
779112116 211020825
380580412 112474561
104663751 481633681
932110417 184223661
197590639 5036593
318048501 26595061
456648648 249821693
67291841 645901465
77535277 244577746
643235308 323336387
371189952 588006145
36532876 431706991
236045965 127491149
395472247 364659052
38632206 67755770
390736228 68871104
3388737 619947057
313716261 473584597
409028769 176694719
95708905 119840897
828764924 399030325
299683790 8346661
75513061 1080398
563736356 111704693
130366459 177497191
274985481 244952978
168572035 501130501
153757117 93507817
372539327 208924653
58007916 246401881
344362351 62199213
354070613 192839376
529802345 242629282
335605117 74936125
57904531 49565881
174785671 654037571
479113909 49097143
309575421 29799498
723952906 284568109
112342297 221655868
690540289 6153645
77712641 320490633
110864841 385003786
594248795 333416429
22537067 18513827
272606225 362969608
510388681 23273159
26183377 299972376
581248513 58665441
538868772 181741223
146862061 96408797
92897713 544330651
40771421 89078036
120712945 802106128
638401001 271977806
62166805 149508799
364185845 4884276
11791081 683946505
51518017 127175760
458881663 313107081
559244241 623046761
676839 556315627
17895469 256273579
101507392 282695323
216523531 47146544
53712575 54225493
316320775 499445157
78897729 517692581
421865065 156123001
641406907 470590303
771270291 286583116
502510321 38709001
5500692 698639852
134968641 856136909
48914815 497680758
42595853 90614826
63575093 365652876
112889577 746362894
671253553 411055326
194500697 107102806
97436011 683266321
215184425 299937967
477342277 18900856
271988028 668247283
137372721 175933275
232073210 302201362
148682511 539568187
351641721 410459
3420703 387537727
29911666 39885035
265687341 129255711
108598929 169746571
476441148 510576454
515172661 314651437
5580121 30909333
90120499 338164757
265902501 187949957
445620341 339787405
601732065 255151807
11645329 78289522
71140861 190579862
866672991 323859558
536264065 63754897
642067539 158321379
15033169 263706243
44701141 432124841
128439016 319488881
560511993 546652466
50006500 12101401
900466907 421759645
113429296 52429171
202557895 152178265
596558305 480070043
732611053 327462337
212524821 342822601
691919706 143704211
654174366 63107371
21115690 324839081
247434453 98846665
94921987 54128443
53421801 5374741
48800701 380993719
373823251 463232659
386468215 243774257
130678701 20124325
3183663 687832801
257303453 353614801
346989517 231132169
82900351 597586769
308630281 32948329
122215393 490420401
232471681 87501385
251864647 143221089
333912615 277304469
688651113 523370485
143340619 753361321
113799887 196327837
171188335 76000672
46492649 29088225
185515907 336107430
585963474 98080376
93570063 664543441
13338809 301668178
17265158 2150153
5781953 558616169
423997807 42413993
411341698 48228368
233915497 26131024
243781912 813759589
874684918 361286224
390074217 822853451
87924621 115977343
95777513 468524116
112794811 474212761
281829916 921428935
376645786 568115137
547020373 2164455
319144945 72696171
9029837 31079731
250509058 198077321
104156697 37423666
182730601 58142473
119593291 625769
856213101 696237913
83399993 776809468
214047466 192303322
225786691 669479571
88331011 173597143
83732617 1405621
368851765 244271833
176610675 28754056
233245707 62351605
275037841 277882077
497077424 6865057
23894581 83481643
36650409 87917409
185591881 189448801
489255715 1949603
374076545 140136203
476618581 462522721
24094561 58410421
7981262 86387813
194378893 175544321
427835673 642313333
315666989 225829951
39353392 590527423
573223561 92310947
415134316 895572280
424950296 504275962
18213166 137329677
307070956 48438781
30572647 663893281
815409545 200292532
73502721 58682021
286846477 297347626
13422081 178434721
285351337 119815351
574838977 63208631
894934741 484466433
222871937 112044409
277741066 11871427
18062705 15632464
151858603 218796215
8055706 254646331
45550417 248208031
39498544 120750257
268994749 175819591
128292672 315984901
40051946 849950586
11093154 631291485
797069302 145576747
296208409 324714961
321421961 55975051
228109346 228540641
765358673 70668025
51753691 66491008
397265752 285333826
750266868 290157448
17216289 115284359
80066031 4289681
13631553 380155225
16392885 602914803
77826155 895711
39569333 774097345
140960665 17109181
574634296 61078465
314595821 46163876
817946481 345233111
347527801 166732555
193734577 249149
601749171 135403705
794229275 553897479
684189979 175414512
533354113 244688137
153477685 113602501
880257249 302423881
1203833 120546779
620609601 727195969
412191331 72991999
534708141 51766749
1846589 400323731
19588438 10317505
587514763 471639453
113068463 7715863
33697518 185235921
522995825 137466874
9342187 460629252
522720952 9829441
262291562 118939203
142457881 401461129
16043126 413048656
30251497 480392914
130274283 69080901
608821193 44423303
52689981 177565431
89917353 30867717
19538183 431710393
530754085 335617777
388405375 415159291
766246061 229419889
204325135 2355937
35712048 317336581
321187846 167413591
117373509 346046041
388922566 86165661
215523225 98884269
7944001 49277041
39878551 33231319
26828929 178565005
624089089 774383213
101687504 98377501
154636373 245838140
674264116 4581606
128407441 122818699
607722409 39303610
40557747 11400071
9442876 18893881
585921982 396564372
167693017 173217601
48739562 104859777
416629081 167780449
29888960 65525461
24461046 6873574
370849333 125412853
91194229 344071660
115612813 601962526
60509731 159062993
429907187 14030044
658091226 667466893
235812331 381171816
617256574 423395506
548219101 529171675
345793709 195128554
30229186 106088221
478470032 127956669
848842999 118524099
180688921 294186451
415232649 1228642
284335220 311236141
96091924 137278625
40669345 552526001
154715826 520416649
480414025 417540319
89778181 518440005
252276550 407792001
239410243 177886557
650414389 671010005
48620617 176386601
347252589 416589405