1000
844362782
241032632
416043866
463874828
470169164
561293600
995662888
334600744
905036935
391768587
997766867
827046622
519744017
475356056
296909603
766355132
153179015
134917058
972138154
394898674
449218082
810165720
851320322
981229884
949970665
292265867
832384009
891385818
340126021
556207245
631508801
629818928
184631390
631619264
786313203
99594365
852330968
350796930
398865787
807127842
446964123
655464381
29560609
536748738
711993859
335297432
193809470
551313082
40371716
330503580
681976742
253766993
123456789
308626884
358919000
750549724
108585180
53607560
776713294
28849486
264119920
463185629
645235959
650123827
190880590
76005576
307336728
759989289
917445056
1
268076075
474237225
795096388
478602441
684175439
405147526
2
905769752
278843658
297096326
927775013
971423013
858571750
630258239
248382961
431431475
355124196
605494336
35956378
190195073
432296903
421966739
862260241
627362205
844342201
234272186
355461992
982631711
64108441
301971942
642981878
13261955
240169458
64250610
7364809
494803093
429220775
940509594
144349431
364255752
934966830
980625944
899315945
695491186
800950105
138469336
172342129
204626073
6499220
369409821
907112015
510460314
350410091
531326666
828234083
391101264
510768791
434763664
317412886
564572638
651673069
933596962
806455187
366870276
691047728
86127057
192280896
535731646
134775154
106540751
139477736
364365547
872082724
534134588
713504869
84329428
451183931
887371686
51026415
880543454
175122237
315198885
105729910
395233424
858127266
731686082
186610707
808993811
923149872
465563155
11905867
610101643
842171303
860191782
6144956
151683678
203306051
750099967
257327513
878094721
247646269
542245819
964695857
69737366
838294247
332107494
233159212
823856509
206567989
784000601
969557165
902055052
735469439
618889813
846578992
738102810
823524068
524611624
385924462
683009102
339064106
858248712
212584791
950494153
56934301
379112186
946023456
153740182
123338819
345306329
936498532
21440620
393411157
821759427
652614784
958694484
969920518
282612790
652195535
552213467
704475997
150827887
608049612
61235900
445181323
908124165
24144196
575214740
613102812
2
547750123
559397851
888573196
914152354
875147384
488725929
1
660786590
955481567
579848671
906617902
950091894
718922686
81750045
125556398
474027313
895146087
846519625
476630836
600830003
321220393
857000702
738046886
133864572
683741683
271651370
97344167
108343462
482378165
324835608
804593241
754816177
826662817
123212968
535411603
1
290279756
70626273
544532795
506726591
690441647
704571649
50241409
633895827
914467010
471537734
941035615
772404036
407705840
36787641
150749694
462354573
425182610
603424771
393699831
315798346
519433531
879963790
984162986
837520817
866616047
147475650
612482288
194983379
646089604
260321921
545426037
840909495
906234044
123456789
827917296
635763500
459407401
283803025
709805035
810155057
669887007
591001134
66075117
263961257
421850338
100678010
64479685
535830299
477782429
196463666
537973298
945592254
205167852
848142505
755312297
182564446
1
913251765
59853131
608242578
740145697
98472630
40541816
796853250
675899264
228748859
969533206
222529552
378805728
826212644
760848708
844334982
835313907
999999937
707093874
84859219
546878075
121355379
475399902
601843656
579418964
552477173
950236728
904515780
202960543
286206110
857659779
436397855
485000518
957105952
216300320
326602023
263066229
179097871
309055606
895152772
929014448
903196295
443668281
177111563
314861890
478734390
497596758
166385402
442551655
711521227
714281736
532634156
488855370
315771346
338876666
449058174
328274204
152452285
729886189
242442008
827749291
349478763
628752671
649501460
723654442
214684309
929652776
650657091
998049421
185980769
719504567
224583152
798324900
624335656
922505374
824028182
790858287
910148009
448718693
527441951
135756076
657892488
79788066
470605243
662697564
155184134
2
719222702
268351413
860572369
83293054
331822809
702267637
728512555
346188127
546181263
575605669
415350267
923516506
203738915
567070830
342150493
222737462
75617308
353491792
653012563
351386828
78152975
852989007
902164054
5862808
498897532
40516221
464595933
871973414
331332087
457966569
543786273
600272662
731470391
117860819
715771761
498265862
974584852
624339693
903683945
732077549
999999937
480470251
725788523
440723029
39051189
841498530
790835137
109972307
53287147
950160685
471616769
514362154
805779932
123456789
3
585487302
2
613215265
389946993
123456789
485304575
569495032
855911423
929080675
496703500
130136616
385649862
952779717
560701176
59659118
919534395
725517552
484854867
620932302
203605496
139428607
83060765
376950275
323784417
567768914
841421721
999999937
767824775
345156711
676022079
869326054
521152730
403968941
986217539
269047877
324174109
316582220
522010743
869785210
742840757
62461517
440733208
127539697
276993787
844240378
42454895
643066747
974711946
866194457
58479101
185724098
966006118
39250073
256197166
907226261
913194626
926355160
187151762
455338200
168850765
432468451
653257411
653715502
238435441
620736104
214702425
369689727
562743396
788546181
751947402
242427252
350379600
141812026
725328772
644617137
620411887
350604629
853842638
169763468
937461814
436287903
503776313
399300634
367192330
2
123456789
775720053
142668831
787086071
933913518
13506768
617769057
834106403
28674789
352018074
68359973
703914876
297767124
743623203
965503252
283952684
674700353
92567603
978576928
995850917
628158937
919666651
267463946
700811138
286522875
825906276
152120599
846617562
468685788
772349116
464873239
3248062
940431603
676526300
947382387
558650871
130874090
204075508
15664059
900220565
51915285
555891203
650792721
770016174
468022920
771930897
441494096
835082227
933733978
117334046
335646072
728339603
755732469
474816872
37321478
234525886
535564237
546761218
951512517
711244591
813425293
933685772
740882359
512103224
473167534
847602478
448085122
850231494
274306490
840470563
334307771
230115136
256009830
448059010
558026046
507466975
999999937
306291800
179426539
13366772
667553811
512325320
580015821
127009580
115688994
752375749
917720787
702352973
754498700
417033959
102724733
168978800
317236431
320782930
162002722
809452719
378520774
356251820
370748199
220736589
983401988
884084397
983307822
631876340
835980540
766942689
599275912
350378331
473107745
840601052
492002648
770797297
430518998
255099193
783162048
907338075
764130104
119140061
477929273
414675837
891124840
503030023
451487505
753574499
958526097
150657015
397459178
640192095
638745141
48478747
392138543
913147302
401698990
762716869
774258504
185865864
171395170
710917328
736507900
494326201
43369837
999999937
11130132
721061937
162320942
644464188
262374498
424866658
417124937
946233149
981177037
937916451
86492678
411810484
17597722
201195386
188822993
216829034
292660945
359605834
806511885
362268705
747689596
103248479
726490955
927640604
230051632
323283662
629042437
346480676
163027718
248939793
85387658
50269741
54589426
152596659
987654321
179454523
356283411
243927887
269071376
662311092
587401123
371007141
419629934
101680271
302017026
568901931
441146343
665189177
591697362
123456789
32439058
614990189
661632536
597797992
981074524
100163851
822894987
40519396
246104927
155624296
597801693
769349756
995506462
137246331
301026485
315065509
285821971
244932612
898447015
987654321
269427595
556978170
688140461
462871898
133332719
320670914
652409112
954601739
999999937
554163154
716945994
612239606
149770809
203554753
1064687
29643588
926979490
314220842
111902122
757027610
270908410
533270080
609151998
794586299
1
554057335
849626917
107766463
196599954
979346978
979347864
862801191
465901945
359251957
941701497
884030379
125975396
239537794
930484508
281905634
841403654
919104796
273861599
254551205
508207508
355360283
43549789
858830444
1000000000
309876069
364448515
572019288
555833929
974802735
363730
973917755
857031182
400364240
559077518
438592889
907283553
827700814
596593219
262774317
922966299
761956591
967132304
580047845
9319370
212946300
968570036
779688722
975544531
216028851
711855036
660346176
673725592
163513097
100044969
797049035
167938297
811376270
396373326
876105598
909134738
326250572
379948195
94093243
544455072
257716679
770376904
367953411
873893835
383758892
281205737
349588820
505269208
438593520
196370641
123456789
873028090
123242668
232765
319763828
170058961
203745530
455800972
230082639
221596582
187625410
159474294
843980097
853300028
268946938
548268471
10300204
203313017
58815307
355865345
574885715
911136757
144499002
2
671456658
273238486
987654321
406993492
299413602
970848085
921101443
469758470
812733400
21359473
996085297
74410592
285314961
495307154
20630931
267471926
233357123
613762220
976286018
705895069
488211075
125857785
302744308
409635499
140773705
206451600
10884006
892321599
205628451
32862378
906488642
166397195
253482047
203157713
567038011
987654321
969814464
120651869
878940591
543928117
24057039
371296796
188129864
652590516
541296590
284653931
277237719
381671243
2
67380655
33281261
224203565
429037768
693490501
149091900
950545393
616107093
808578337
826370088
667617339
904834858
484392651
919606533
67949056
939463512
886396719
890606794
171727761
987654321
937004456
904121773
912926794
394727459
987654321
527141697
201043006
155876453
791988815
625232467
73613088
711936197
952084168
217005196
980192246
511894499
368027685
963316289
415344113
531359405
642806534
898869494
1
107852751
580276822
286359684
45374605
69230311
829983808
613146024
165209809
568295440
286505747
225805858
268926085
396467112
527913786
83947377
928473865
816720222
344342304
73851392
68537154
733669344
617642399
33146217
968434655
929993182
139519398
192187104
577529204
508270370
390670456
272497643
567838680
603729300
203791145