1000
671820935
914912764
656799149
197982102
990565474
899749517
73705187
220901796
806526653
337073418
64249374
609786717
721524097
666222078
875007930
259363610
937103746
407210598
166287147
937365359
621922874
465678574
474940717
704998232
439553797
963442886
973833694
717529703
389963204
889912198
980846904
224323120
858312202
998310619
77036417
920070369
5714474
194769489
25171287
745239683
851575464
491040516
658640648
525443785
993733026
608729856
143971337
317678071
845888213
36431013
247277063
418796476
417870526
776077992
393065968
964172691
849470406
981685952
245293054
660846278
161175948
827798765
787575919
624538917
586879250
84390252
143647853
618354277
194635377
601985265
425847089
296315881
399968791
810504890
345931472
350559991
691626883
245643813
237670856
905201997
414069847
341807128
407109284
813719517
817892112
446406140
876298393
993309884
874921478
774433722
273540367
487428048
976525787
785421503
1
678064395
10810094
264347227
585916521
845993126
765747253
11152648
603580668
749239660
332764839
613848091
399478410
641551067
676380857
527253284
305157900
276281045
106509829
307324437
250583162
135481699
775628127
320438481
156939641
34045975
417698514
514744802
284354716
19511610
197189457
343042570
474857140
254686787
83977364
833259170
347490261
582837761
517393952
301887601
127728131
123456789
774926575
795270217
153228046
523562673
263334375
26233003
336944843
688309965
482624833
555073289
744737822
752533086
361697196
603973846
186135140
45843074
429009745
481886074
812327270
468532528
163604538
68107378
458596403
737747249
5921693
519978265
745355642
87807052
632757368
958842166
61685716
934031078
973621213
20044460
123456789
165313578
888136789
318701044
541046715
883190736
734279043
250463187
443892093
713662504
443510583
140568345
691025595
448138741
945658231
42366680
99003041
756079632
636752062
40037150
249545784
829348611
287008300
766730142
251866999
627925628
15072926
989101975
901427581
430222179
838683460
538039353
940321558
621475304
762329618
269510814
55776033
831420588
227952269
990034394
201668770
989397629
562301492
532062000
654690613
886181315
907958990
843252675
387808982
936633144
200952245
39358180
155575111
451192627
763785502
905712601
304095828
303967273
334150834
118790566
709738205
763626192
392503312
180489730
931468184
355095075
412745143
211970364
387792955
729499877
830814279
999999937
885789898
520215833
861410980
263504551
260248193
910575917
954883911
622534059
893401685
524226488
854768740
796265703
661615646
938959185
686302667
898905683
703194062
677944354
736079478
253008962
19391174
698364888
137508872
218383870
305242527
263026962
129548468
187265779
313059354
159664684
683668613
429517839
473137923
80240339
959610076
152792589
44333275
2
519364638
692943557
977376212
105463972
282762339
484489172
636170473
399758289
818193418
319481800
340802509
937852585
607463541
526453506
62044896
542188260
82911166
87146472
749037021
415157105
855083181
778178679
508709281
344750141
293629571
250572271
467406714
531196250
878954132
594990215
746061938
903674832
701116486
464169022
933428243
705633370
911727579
999999937
53199296
588974901
682576890
434678584
974712292
140056434
143649785
281499909
290221505
601781622
969059442
23182347
429147002
937936757
817277946
201089879
819733337
995803775
634415950
112364357
461825355
446900122
535256883
307262171
598671228
784351682
581932080
312094678
53524638
449922857
696437291
139306526
52660903
530131869
386010920
303103204
760119639
573106722
328589569
738744438
770907651
600507685
164449429
690160505
826586804
287746214
880680372
257761257
49769170
92486817
709531736
652902153
121871488
5108309
613278471
339611066
168723229
657692976
264196403
496343482
589031791
991270545
761920759
95746780
662029778
917591389
3
646360719
598086672
839336894
896191519
46743511
147898435
65977852
34346458
917985505
487119443
584413694
552356704
383318077
70860784
637523805
997223018
353071253
765440549
402116953
927937438
486253325
938010174
88312349
892547175
884081164
818787300
813015129
575879817
260949092
988607234
817658140
747615060
572843039
205468988
987654321
972532882
84579589
107063321
235725623
886904554
754085427
82162778
100588451
583962539
216992337
9583878
187159376
2546698
253138710
942921008
96594680
669124967
906697077
442062143
954614912
388055924
153902815
354089507
966151677
556111027
261706222
73656179
525043688
241223999
747525788
234155694
423718272
757778275
946794179
673405576
285667813
642381848
840823458
73794917
976115272
499324041
713871520
561996937
422212174
282700487
715956312
212551732
987654321
280771011
123456789
221544931
84712308
968887891
498217067
96134094
37255010
624637061
848079748
880874730
115317344
34287817
48371603
336124202
969107711
210736737
590590249
855878079
349140451
134444855
786202674
154229434
514083545
645183065
301635626
625087992
669940433
231607098
473995204
460698301
93772285
327212195
29000472
699219109
335628825
226294149
810870528
749121326
990487349
566960155
160980947
119698582
777558340
484135716
343183325
865556154
928270853
880512576
53681468
389849508
48792091
500840072
540399056
660076543
642218145
712175974
45260369
455688794
931767927
123456789
754992518
39658959
615787958
584834899
798543879
96820227
177292465
48463826
500139708
401413708
391088721
295461390
493581550
835682985
125357952
105078606
262055824
296673778
276438535
446273558
215674035
861859342
69908774
530031611
812878998
10556102
901315720
506215335
1
132151384
112352259
503781892
619859751
553579998
944828903
968168970
340672371
567278040
715125309
304663228
569475368
899022913
547690228
706367949
127691091
282134272
643486735
957414098
222476977
231384926
161866321
436084379
740004327
561003981
3
309134793
539850353
517683663
757603638
289861060
656037688
947069617
563536435
553673102
45165377
673958252
465400032
325341338
32901036
26419917
215268405
138822169
479570604
468654596
404865668
398859943
153491875
608447304
713162007
493869538
996766828
959832187
241368388
975201861
922800949
981564261
458014721
894231325
468307440
120430702
749624900
1
375846174
1000000000
702671661
16161369
47321796
417357590
327301912
134020619
171069831
72240120
561841970
310396531
495279507
991598818
127390743
283583654
833669448
3
337748608
367038820
426788629
48476750
953453737
308894049
242747115
213811420
341868414
239108408
51536943
438604658
526529261
413923077
65236637
987654321
424589038
759901626
325699552
242723752
450721565
58583565
818228756
592816705
497664625
338077765
870797031
322990630
80771410
376948046
163514045
929893333
785950298
582161753
331167005
727599705
60749762
624496469
123456789
299126944
333299066
996040817
814530647
613671117
14462818
789266776
948733157
450659688
346575302
432957773
122301716
315445045
767977562
975839044
784047856
560442514
395300605
349851453
997551491
665079257
500134521
995506191
912451906
730719201
898638914
835565304
267974389
298749436
124042273
721516361
163718969
999999937
290190885
852670595
976609616
294269534
966002288
38776970
938485681
209491000
984894666
174424520
268988258
533110129
459462018
826063556
429464131
710443184
622111171
542898644
428122444
333869084
442667532
163484775
322748002
668874831
544431128
171275254
62337429
355540258
835879164
846465982
758174435
232644493
520554320
658818880
986626505
51135215
790904573
910888391
2906491
469652084
558099884
728038390
367279705
386451236
858936570
292732835
297558086
133636650
871761164
852539587
891384780
936305310
987202246
782518675
388699734
172738562
193367467
43819495
872319581
828919582
605473534
560932807
392125800
883779226
598382099
579701859
477538819
456288388
341133418
755127800
123456789
312893713
234861357
810485074
697290079
411995531
918360675
608390204
82430760
426797606
244539098
741869844
3
20511843
394943229
250440020
1
601975561
435450990
67540327
8017154
852468864
670078623
789421542
151517989
295482594
58911471
645115588
838601757
499361967
809585469
864152261
242763004
147683945
506849120
476110683
37682886
600683033
672114587
45640530
898948822
68562391
256541317
849602280
883897985
647527784
802443292
82190522
683055882
822129220
299184423
442620976
284515949
320630603
997181704
879085786
987654321
16758877
249396963
917639000
874130213
597654383
751832036
204011407
208535316
596503221
547812258
355017061
442543115
658212387
146348308
972087728
123687041
449636183
239826199
745500403
494304786
321646740
793841235
419073113
314980999
926721553
157634562
327205049
462409590
819244705
149271546
500294740
369428210
350973482
482469928
406394179
428415537
18288811
349198820
124561421
862796428
684583987
858135147
858135366
496614887
864725783
630929652
806282945
806477051
722146381
61002890
966798164
527367352
431890511
982052055
101588940
893467499
84146546
218818603
254457383
853752002
473068922
997209949
302152536
265622274
226238303
693903573
747736747
421187993
596477030
373348353
241817756
801665859
335460192
652720222
191262543
96142490
90275977
980986489
146336686
54177789
580141082
591215911
742477274
244470675
94772774
416729092
445401179
40970004
989300837
46718098
104405790
649904130
326212260
552715006
681492721
995608691
679271681
782520722
28196828
172865050
730337289
849419753
759377819
408299709
715844291
504851922
153222945
877358015
98560365
618280195
15499446
781066362
205878330
126950564
108791990
489789789
509547596
502295081
256456876
752310547
206065140
3
508593484
926855099
737142305
964897609
557567743
157435514
269029779
927632225
473149292
11821723
778928308
456545324
205357510
807006843
741673324
53812093
18365457
879119225
592998570
772633034
512830201
304955283
186190328
431767509
278197877
114543447
318631876
544073214
797109203
528961521
936692345
736078188
5332523
861653376
366532809
365620148
5913280
36842264
902782489
157324066