1000
315027976
426274138
445073258
372720018
517635272
804040179
4255351
3
895876882
72066636
127948110
934909961
738816307
868144260
704237180
593800527
122365096
883310021
736591762
364150283
162384323
93295798
1
807569459
356445901
552199647
350698174
452091960
719778856
414558613
821925288
986944049
693101858
612087446
160499324
476794145
239348870
51571626
306495412
962130550
749147915
274650839
107277616
58404189
216708330
629652017
710907656
658154201
589983398
786142544
735421362
558431982
123456789
945631835
479618268
135894112
99731988
135889242
623695018
430567390
643711752
936765877
423751210
128135537
407295364
246602051
700657605
209655223
508405239
789236422
625944037
717592597
934106535
553199737
789041634
513691646
612695629
660863908
410086987
162134323
807709199
427664905
402530512
255381689
196635593
636951460
971995097
181371481
87696391
686502078
624378102
1
780222797
242012565
734119201
896937383
965791368
888214236
613707057
877061026
379720139
845396635
494215929
728160218
441114202
437352082
24565616
423071213
417179136
123456789
739661186
277866233
356875717
230405682
322532855
267207615
529848472
949559818
75518905
703271577
772006474
782556169
910115658
494322647
19761942
240189976
118134718
772421852
502450395
525604664
438431427
405076570
772938914
102696976
745281682
119114323
664606423
638911254
947373975
707927740
854663677
863772390
260861861
379354370
312597744
607519133
346288594
607365968
433823577
940622046
979975354
438369190
531304735
630269044
986361457
262071576
490537278
417950438
782989096
354471269
677518162
545224222
761876660
992588784
930197514
616647924
885240887
340638455
249027580
976592680
487036240
999099734
61170682
244346492
852183064
315919290
3
709186151
835405007
883721255
624934419
277041706
24756354
602385953
696812610
825066634
705406908
604435496
174091083
704799326
776701501
920146198
115447062
112864882
722352050
508911604
536116578
630451002
765775107
117340386
3714187
842241479
992523927
660997159
819286011
76854443
436775610
760383265
565225917
886553871
919266031
893049778
73085433
152341183
399191176
626519210
998599971
242502699
518306714
196333664
347778388
291907452
202687497
975507330
53319040
583773483
76204327
798670604
784399616
938543902
492371281
591523199
458604263
921591206
674045657
97320777
423785354
392918810
117271061
285726676
374975694
868523434
30477088
258219422
528647547
581508582
104960328
614694095
616055774
898277891
1000000000
867080826
86041222
242147662
43463683
97442781
178813099
146262791
498726278
578248530
960230480
882746691
532538534
883989512
450626279
957147515
370838305
429092053
51304674
46462993
524255252
765880633
547167329
58968128
771064107
378340147
316662845
390880181
537745112
137406337
812614117
38861900
1
199590958
382123033
883937468
426582702
241812618
716749324
349588121
538771120
578612745
793830146
727205351
982549376
3
174188350
447900659
452606314
229052724
406814808
452950591
176442492
350297734
340830023
197697231
369194701
714474580
978004678
809808545
321942684
978982053
870532667
99511943
665813770
689104584
230394705
287208213
839276207
888260020
57155943
782037859
473041146
34637373
253780834
26101373
436687900
760142299
295496139
32220372
304340843
336015665
573093267
290735959
273922002
940361091
756510197
921793218
691024940
239998512
389429156
905546626
230956311
240684041
399455295
595942760
157504811
908719662
10397024
365865632
603871515
547311915
374913467
922212944
874244076
832970396
855417182
268101000
999999937
866570868
427188193
485670622
390226960
362565490
204547179
668161536
744058670
92221296
280930577
448745538
421051217
205251432
423839976
408543779
655219633
507130861
343064887
148659512
655000608
286795403
592924852
20818913
995884431
972885345
905278628
143486246
879892854
224867325
512359100
81007117
588046242
55731605
2
529427474
767977980
641723619
412942192
734880871
12632841
462823824
837835519
804458326
121388711
471331100
502133008
638555331
981238784
925719397
220352820
706440333
774899552
183083253
26380660
556810483
300737120
302897140
775621880
746403203
224570278
439687474
417766959
272718163
352033749
488227387
619599359
157333527
439121073
226867278
388530629
524628
609959071
317055760
827428223
667481520
539014405
174150777
751499153
591836469
861510787
548060625
531861129
88198906
856048260
870276333
874978681
20613322
1000000000
465360372
893973467
215837779
664822190
715654902
327052150
399429503
983662078
62065671
57837462
318303721
995803393
775122732
419519388
954145594
151611755
264872460
390697095
637514374
42641936
358706277
815109594
311094311
434920516
638525301
899499412
842567310
780109842
270645996
246158603
842433060
2
688640822
374079152
665089092
811746032
654097673
564148578
15123503
183746694
19983032
214023398
156947808
577404243
657191186
367466707
244329241
200224323
838504003
845635645
320417952
28007619
442672010
222117110
13327121
699664875
110175069
448434991
670834652
276243105
174862188
375280071
463868282
302515685
792819330
741963968
824559428
736330229
404286645
266180000
641858539
907044037
59861353
390679276
42142205
141247944
590843246
68452179
879836978
928700579
209950290
643477190
556237741
875652422
732068896
743053290
828930661
915004792
80273797
46775539
135701656
44284246
868571927
861053821
489800345
318823992
392131797
869184772
925503666
255024001
171387764
760509634
795955982
167371681
964566495
595436417
803012843
73660470
495015461
198269545
436639715
124824083
114921148
635626567
52104585
972351627
511272679
676224995
847716643
421304212
52099033
27665145
510769993
285369717
194857377
500270287
45079439
467499112
442959595
668255519
1
1
421422296
852346228
171134227
801489352
32715384
561550655
481846636
959119770
935311138
236693262
827839708
608264603
556076389
510684426
912353652
330876742
1
302646299
411512444
664626750
616390125
900224347
12297111
663830401
243800151
396515160
48970963
834891289
936013661
747062966
565150758
698272430
8430448
2
221994848
115147520
875815356
232628091
93265477
70443946
537589837
717925459
261053112
50340838
75762426
367903493
69448100
318471411
348656329
526210134
433748994
329970076
982112887
293441427
353812716
170362283
58216117
750284329
774736410
949421845
917119045
675828396
261113627
790704048
577188562
758427757
1000000000
692151046
191681358
894661335
905689963
114719491
123456789
34326377
981427500
565674700
72063788
2
968623385
255478912
828454705
632575384
701976385
327868897
780350495
551434806
973667359
734012673
169022844
442915114
678712424
387028548
734078934
141043656
470598191
937199050
571179806
214130064
35128777
107001700
218131810
648873115
87140971
958994748
240855264
940435861
648046928
514301458
41226184
158855264
107995492
799515258
500121885
3
201568499
875496993
401846221
316793732
778372276
701837746
178257341
846382632
322238417
618650043
344250301
177230936
813069603
73518534
157541330
430154237
625217499
779625194
999999937
630390339
446593279
92046717
85027505
54205975
657423129
483554120
361316369
80499894
982626199
207696477
42867180
420124834
454767975
663417005
422461029
537942961
741434496
658126519
813160792
846779769
542490559
53157495
725175128
447550432
922584393
116773335
969027026
750514287
807715255
744318562
553693468
513683300
687965021
314941838
768350436
656587626
14149850
726792715
1476155
624293472
34605996
39574593
182072490
956661895
406945003
901449131
947760597
889735429
322469274
72555952
303381535
3
23586091
507238997
251776080
407114843
539898143
594867157
260856434
891028221
170787529
381673578
944411588
149905044
322859720
770191224
325160799
506909024
850718655
987825073
914712362
123456789
327610984
131858508
819677551
468605894
520942519
23665690
181801140
784338285
401713696
102200628
274828636
795360976
830434366
618563119
249828412
85799813
868194734
645719952
979496217
921870097
320679758
990116132
2
834517871
2
987654321
798071194
288778397
445376098
973232474
116730174
26337042
729138234
751672059
812858202
300175535
852595862
290781035
682733919
116114709
908655561
3
777628504
316282079
999999937
333062089
987654321
258569793
656567155
779990736
809348844
543381228
791907492
166215490
472682095
638380009
587100003
3
451756693
837258767
1
752759243
805834647
177093113
876708600
184613222
494206398
859017250
666519528
36210383
948095201
309833257
885282674
680012652
474642611
921758844
343898106
517366409
374345347
311976653
180416543
265635891
357239102
918402981
888890253
234310974
160370533
716353611
958093915
249860983
62243333
243274275
146242756
765098352
123456789
100306685
612555997
112946662
941091819
325192243
255887397
751880530
563939516
271303048
573457475
504797605
350902734
930543341
525376045
794501763
878638152
177959120
774533087
119789692
786495368
230559122
542793990
309997807
925491235
630698592
357220651
876306713
520443008
637261036
446127947
889502443
266856917
757860478
762185248
1000000000
751427856
561472014
628539103
937922845
670777326
981932116
427883808
277832742
321946060
252771660
776569336
385805205
916006336
522475364
4583008
56386413
953694651
333643783
671489241
85949279
369025808
787993284
156561090
98812964
695264411
547479079
217262595
183500076
283962059
155182843
198007958
749901817
347689028
2
65480678
525522061
146631711
861507904
516267005
757248521
14447077
260385568
440026222
87617299
960697246
816560505
513041086
30050283
248746577
334025114
33627639
833577493
373861324
390730753
527891447
592932957
446321831
893327029
653616932
921188686
364972504
287376042
733035397
397727205
533657008
607802858
603965859
328687668
68821665
132058555
232872801
398356112
294880707
460690682
282531773
999183826
756704364
396315912
824866360
159259284
748677259
705021512
812286851
952276548
295542644