1000
93940593
477944373
184288178
579633971
817235792
990899856
545549852
200652869
341003688
395290026
143507862
437685993
105974712
123456789
662522495
288476738
634830240
880605916
1000000000
775524331
861463592
155211501
282482967
836489179
367663889
359477359
380277698
330591921
304695377
457248023
987654321
667772220
123456789
908858781
678006137
560388987
804008966
895213682
875115717
160646873
978716731
47943056
106244490
914665892
759387115
210873032
302775316
567741627
76316513
108052176
107523407
574974832
522194349
421759821
180608081
448415380
358044124
451830923
740372176
769656489
897994696
640663519
953583982
146028382
969612719
52759618
706604563
707272789
436579901
963956857
786385493
772846363
222697202
289821577
748691087
446141871
236517973
196098917
211906641
452604681
892127760
626215565
269708467
308591241
101453884
125495050
487888526
355410922
953516480
999999937
320810625
857394908
131959140
889658847
200501449
305976545
668403439
490646220
742993398
244640540
969674051
806642810
903283873
48922160
287332432
986332855
62525604
713535112
458920727
273195686
201205033
321295420
459650548
665036768
217163962
430399870
793950656
994043726
808740795
2957863
76451878
850150663
25263033
842498015
987654321
452706079
26655869
185073908
421178435
9763596
573864043
56122098
883948945
907300063
859141780
2670749
272759
730048572
893706285
472807496
369877007
432057599
598727290
546408842
819228529
842922760
721246763
87481289
255221455
744173374
294931378
743297547
654310069
718471374
973013243
653478586
380565700
21203068
147034051
475432786
289164381
156575428
293245627
720246163
896649695
810546997
223980991
494456012
147803871
271111134
877990562
288263330
412599148
247473438
30110428
832131113
244649505
789068421
736263356
224981902
392875774
323828487
500148794
176937374
560712502
823404065
201187353
542572344
900995214
531001105
865766759
563865917
76154902
871676186
601991960
606028778
462701255
738435429
297763831
1000000000
812734199
71268600
75569188
784824106
376301195
308891974
890255879
242809361
586414966
935980790
140980847
530698786
479835958
425477349
807190062
422461744
256452903
733679649
506739549
596622059
165470645
526759639
66947173
425279225
183406001
11579912
364588919
147376067
25321930
629155410
703964358
442443750
834971944
927412974
231750297
868870868
809195751
37032049
298633650
193397085
268689062
717037049
569649853
523980375
927619871
477721475
319136328
838375397
977802998
628936813
213720605
656824159
499435975
451306518
362435626
929572432
258426056
899695539
855382054
602324350
592328408
836258321
987654321
820658502
732556754
322967757
584465364
626626632
442307610
356479104
817610465
304913560
508063767
42340464
442929193
326671554
284773073
464016841
457457588
795117910
137576580
701652221
83287456
921347035
907199940
28571243
5647999
266449063
574872755
517629594
529800853
914387686
929856701
354634063
268156121
24378695
430212243
40434718
777800807
229005664
746609731
730246164
884230093
670144550
719715180
511526681
775487841
689837201
526765314
261517741
642407377
711939449
77769737
768052080
148732183
621186528
613114388
246970543
884147264
452201334
116655471
280123004
301323140
642696720
343140948
751791601
920266432
406037403
959845120
332292742
323913065
586328625
956929047
889685756
531599315
425692076
142042091
997582715
420229396
828049070
190640669
746128439
757433013
109263141
932022946
389207966
86968439
483938744
968715069
95596309
515747259
109858225
362802519
400446027
60171030
168839975
191076137
26396255
964896461
650789733
929353932
281917672
224735326
546447630
82241976
429363671
246496572
30670212
45367467
271060389
802326669
987654321
221300091
231509240
836333452
163116623
985571146
692578550
694463346
751216373
319171699
953506486
56572912
123456789
535400589
776604107
432525225
405300873
980271141
791730088
767289090
99457385
608613405
846052298
548333087
258326818
288721400
448273470
29237736
948474292
571320211
786296601
16859261
178025427
781229025
384601330
908546351
54354327
291636246
800144663
324560776
587354059
2
615216352
866307925
151112371
957036841
82283003
395261492
638184275
143351969
680637078
218740586
474223428
683211699
366532221
233093724
137314835
958369034
197364665
614124995
736785976
317398218
955324626
342158968
106547916
73590979
397940202
429913270
267440245
594651866
890948789
823556150
743786022
1
12913685
533639203
491435901
261782169
201522577
238058098
376971240
121220083
772803765
459364377
258373598
134929185
220153454
8078108
845207223
223686562
975626998
84494788
565509942
705370599
527179285
35118009
2
654193883
502485219
205329823
169748099
737791578
781799457
220888654
7160727
257420215
839644931
640835522
931669842
723897074
427855048
120783636
957375752
514173766
364365979
943797092
36211773
964325417
356321390
934540809
518050335
219504047
117071643
225282463
477953573
931865004
514195485
739354964
843197729
804667934
261128838
404273245
766734437
640880818
297295842
653777185
925109713
979587808
290103886
266416176
374673237
791561355
501620658
204774356
207559171
140759615
524735157
349668557
770856779
962793467
669878505
53113209
243399700
947883595
600916043
677434355
148953296
945842138
701939407
516506180
953225028
154984844
61124165
156240579
998222165
423746427
976156830
28400613
742117912
615802058
494851533
137386048
858550798
56165809
671428784
704779939
313899123
89030492
538762920
91369566
667607772
940147834
736116881
61119459
817052705
786335908
700578290
149087679
248585769
953401354
312582212
616640560
675244791
386072354
284812113
220219080
131466906
643596120
347343847
945940419
416088907
568449564
822473506
462264899
881938278
969842975
239747765
381750738
219662478
406699922
301891995
422139436
488857491
619752402
214970592
836817027
808697268
757808246
549786099
965493773
915828969
445232557
228190922
997008911
1000000000
471402676
187188574
920590213
492305464
362425952
526439483
603525909
1000000000
231202233
2
448894190
869900035
215412512
686216847
522256872
250839765
392967343
506727109
636007117
82040586
994031038
155983468
962623360
961734083
283370593
892841558
418599782
782914597
889345325
978767763
995703388
1
29279798
552986756
264206673
19991103
337554207
728312564
113381143
688114281
150842633
874928902
743851442
548269524
2
502130144
9699249
278390011
241933280
298028263
676075141
132807473
879493887
940620536
647803720
63603250
506867163
28919093
701479266
910355808
669276303
310483153
11564043
395852535
728684130
790076265
601044218
609559282
668110918
706405363
969727567
208617437
178115773
902780757
1
825679642
623793286
685128452
356946246
298438051
847841119
806587469
847581937
698030605
205893032
619247676
492144405
253741294
305925625
127515999
964558329
256837304
640513680
542986568
142486010
988539305
782886015
715029544
571728067
964268984
329673096
267790765
692743453
472921626
441150530
805202357
167518126
79727689
85699581
210703488
242145311
273977719
881190415
864639227
217801785
964794741
193480793
333421344
42725833
767046504
113407464
967505500
814836845
999999937
700830571
823367980
755959330
611488928
281826012
457120346
441393961
231117006
678307483
778709673
349612578
505785472
5010924
875075602
511125408
461576049
957475778
725272052
211186817
578209901
813274764
367811030
469561124
906229990
688352082
222890874
721504054
664318901
9038790
704818047
918953027
57670839
227546163
609872493
838158289
323853270
381769156
422043200
429177688
432947157
123456789
500372112
350901244
766797767
577994747
235283058
138662866
366169195
722471071
867707475
303382403
418358725
110353446
314483136
986574130
301320638
492578068
394872754
170998219
507502466
537510966
532303001
986906474
987928512
474098375
886871181
584031483
572820456
30466550
164520443
737255530
194909337
4283938
174033909
501244792
869247566
827303706
979050955
692451352
16141882
753499796
434067045
338465882
40140488
48204447
190370123
581101284
541439394
375929689
628095836
812337217
564595049
371746888
703700720
63723884
493672026
4028668
110084011
391865586
191034706
996222715
576816273
72127601
361505577
224492723
418451757
210293256
740247564
131944369
878839686
281455478
863629920
5297861
792427621
567956294
537895726
438639179
735884949
821537760
993212939
106981633
25689280
662945704
171672829
420115138
806352083
296766968
911915294
734731300
475122673
730754451
577018685
461313231
151063664
846152712
868178752
758022970
221057631
700426700
69242207
358103669
799536272
826536440
999451236
615370888
86075540
644338301
153902413
637173168
666242099
866449538
833753710
420150970
959507748
181189090
92728263
642326195
436381399
674762749
1
998812254
723751489
565204079
588116347
728738178
735328085
688296924
235571701
596507999
551071183
765844643
155870601
258830161
996375384
1490882
741068888
103570510
156179500
110818353
444325353
360891481
369692632
514223166
889079037
953942195
593394807
435090011
478814873
8710160
94207662
146536249
39404504
534278705
515892266
918502650
570976796
715100702
43998507
119716768
893474613
417482631
734832805
261170054
18319444
355241602
903716265
961303904
373097120
571460321
921711546
463050619
9212625
123568140
358598890
7251222
860286226
412671618
497341343
999734322
1
152116447
773588245
2
789283414
125366488
559075741
729976321
588397751
217112867
922987823
855645113
40646288
268550880
925122268
595738918
276806339
665741176
187355159
133454953
966728249
451558841
551531032
994377007
376020706
499447303
611169268
537024516
488845539
88485080
457500581
112042695
526042213
264529903
503766329
521826408
901891426
332363854
479897161
611752157
872066407
294748646
513164242
629956522
122613035
741690716
602382797
32458655
689074133
476206162
886613123
853262715
805001589
605488359
595582133
898709096
789350441
898105902
467547300
843420576
614156313