1000
338257222
181034569
667508009
1000000000
707841242
608490250
924541450
162487566
868894288
640817202
760982690
262063720
698406884
853979681
98603834
316934773
639355268
262471997
764950047
543321722
463237400
595419792
314497737
562721917
960698787
829272738
515244228
487728642
234911328
213433172
772776670
227909017
758793027
978729649
566274786
606590604
524186663
409000817
133140635
203264967
222483397
636965612
889699301
351853350
174709625
520832687
623192167
479103803
814415520
153533707
956140914
182384876
741646108
725010384
843493067
641067020
823599535
469350134
834664476
43276014
77438254
636856687
778792604
568359326
790991736
898170451
228983768
240560661
472983920
417260201
346923066
477881686
571894531
854100696
576162364
173916513
414347138
395134743
401490133
395320443
970009120
351840104
460527283
462782510
235549308
954633661
663925158
560020231
246043224
347338823
966716684
976445885
133673197
226944200
402723298
381105251
628229963
331612114
610342598
847336108
445070450
964448273
452390473
538593919
406020585
116213731
752358811
602015326
278474666
853614617
346571534
194902270
571390886
446768989
98163443
883281215
3
127221193
576031145
926357674
1
480120353
123456789
408857677
643622698
282790899
46792777
977788409
216529850
958863467
991180111
30777415
937171147
125548934
24324674
980718205
808628543
179609588
258753838
364253030
352411946
212271938
388043068
756231016
219739867
741459968
109489983
13234934
560534924
37322881
537486005
401661091
14214647
788223522
906880616
859840320
411942775
217714632
123456789
502577543
966354165
402359574
546996528
318384071
762017508
242686588
776726358
340687785
617572662
945598916
732234886
88248260
456581584
435299298
7183063
860505868
511209654
393760254
403402824
159811970
538123639
707772849
3
678400627
256908723
339339674
853388372
437904152
232654772
126158200
628926718
569120791
155361566
3
435815470
740950237
757484506
462097185
152693603
620006580
294715698
663957604
118259930
833657555
917897751
923757360
988498583
246797069
6993119
1000000000
311094885
765401150
34778925
537828155
544185711
873019505
476660629
572048604
456123594
544748214
371201927
122656005
620582755
1
509098880
849314899
63517033
435249616
391609077
711010441
167638119
53640472
813039763
708223996
307282051
123456789
258175444
481400073
662238380
867286714
44636439
212201512
497915372
626888596
219864663
415467580
790183999
652002785
471085311
75286523
861838357
522659116
47610037
40003284
988896556
720634466
77425468
214840969
970655652
102407269
767514378
509815177
125755519
526244957
781550733
759943509
600728931
601488276
157978724
738643856
825912760
354176879
113320961
221442642
714104087
899306333
173368850
853633773
133424380
992091693
369263671
791650964
293747074
262373008
684549677
340222304
945373741
917465550
811607024
69311658
454714439
265296774
104159688
988521474
508689831
116820488
869782376
30239095
23424343
886459416
847919215
999999937
153519159
479224365
943801615
981651913
199267378
875320536
638530749
469511300
144865780
8120123
152516352
559261150
622515445
53229810
123456789
498302766
669272455
264690332
814473086
827903475
867496793
135315594
305483006
357039486
58227680
924261848
576432992
724266431
673571008
511562569
581424011
836759282
779273989
276915994
252790973
677144009
879983809
806651415
615824598
562056050
922956226
690705803
588162251
385747974
131034909
980679816
2
65133172
622325037
43063252
561161728
783551864
623854583
775146510
420655448
82604778
805253614
15891049
821381990
915218211
688083035
136751185
246036233
215291102
405647446
221527955
790921103
612438069
156336680
238067803
28939711
568982578
658295830
10980088
6337672
483340013
544789897
235807072
520179480
967906474
124201153
60765127
820263226
769252806
85144085
601105412
296503671
610095520
206117313
37399880
281249119
320686408
789714156
99023331
285758226
473018086
164155542
2
842093719
875828742
489259838
999999937
715734080
171634941
982111612
806045391
75028190
939861269
576014728
838782863
36137606
495026382
87587581
296688915
133319933
723664763
521343380
859562936
699434054
575673473
397669563
127908490
446653669
192743442
650133322
741563347
688689636
526511100
957533542
180783606
878940296
455415443
582666166
434658322
651599063
440755109
577046624
683816317
857084994
136234784
701038824
363104531
992039981
403204920
725847111
752382004
934192168
785544409
14456762
979907869
60409991
127894045
436600122
307843961
152455110
909302898
896702542
970736640
139479331
683211180
791419744
913492362
197109016
429249079
135603048
887951748
813866098
359404230
448257595
783271694
183547427
74993661
271976616
242455677
795916699
351538119
905941372
999999937
941902704
207491204
847908272
136565698
773943521
927639810
663739710
567535743
804317335
837818867
699742168
10707578
415292258
558519477
580589309
894019783
541459532
970887962
2
131365920
739654216
313534215
243703866
873599464
804354536
696111721
636260617
967572055
194678035
3
285407209
801819187
604560907
460998119
987654321
382683924
349474673
971273872
652170397
314870218
42005744
666374583
546969298
450430574
420227444
611922082
288362502
327726841
393072225
412784406
633623056
938356876
112839112
136694078
191284630
980159966
746720789
995749994
166755368
299102201
973347218
944616625
572012445
726260178
561760546
14556284
721854039
645600398
265548147
105653815
53287704
462438103
242162673
907329810
855132723
239604659
234195601
961840607
887506430
738019952
144058262
88049683
175116924
166525207
891125614
938181690
795392564
220170287
924522520
567287266
123456789
492866848
240138881
1
338516876
724963513
201621506
493548307
644623860
705568146
279654368
983918793
281727456
883428262
359424402
257806377
524473058
470529165
622674418
337944255
217359732
170579769
540413725
913671761
155492595
89155480
59870378
588950672
454721931
529844533
710151248
294380877
125354770
466177772
553490936
414578735
796931157
470447628
121315040
747689932
496639623
73046177
342008282
88971550
184921483
819343841
443258994
782723451
211966630
947629633
683018685
384473391
938758033
914370307
745107380
776641797
195380051
515820004
726851194
910607335
30475461
792767370
729492574
389788213
787970697
502292788
941731632
74882930
771866971
958573280
354805346
666836636
660719590
259149037
252139385
314789862
959872916
596733428
484291090
522035088
942084562
970988298
315978330
968724505
689479389
1000000000
429817148
184888179
976084635
33755518
960732213
970846182
960284933
564720394
514959446
15007521
780164460
603479313
56452696
831794647
648365797
986482725
484545029
669845153
987654321
596814875
782369446
123456789
311751961
925664197
84651209
181640789
34064679
483640710
991058434
277774842
279802022
514961253
482448852
607571912
78241791
508553689
773697386
433732358
275340174
287691280
184936420
123456789
767840928
447035318
284173165
534542545
865499433
148116622
703469714
685135753
990800295
736623245
568350870
960907728
303552921
616505475
680513782
833965958
301032672
18290590
71868468
855251615
969048003
258852230
155729588
321306693
567655534
115722844
653594595
972323558
220868477
550286393
204336449
515561394
747582024
575019256
681876663
644597380
927008814
178428509
24468527
688527387
999999937
24421885
114405533
159748385
626803219
130036286
301610698
2
296200449
167178771
727269641
187082829
196998738
303582864
966441795
663009819
804915514
827131415
801431017
357342776
22284768
913066981
882197365
996552083
37571926
344319813
254636678
750048516
382880513
49446530
337324000
527235234
538916559
554287701
782427522
631703333
742063109
424120786
653653355
810923388
9807613
471615797
722962382
418350132
296274092
56672236
353428369
979379334
432435676
793553946
840062095
319447704
751431547
504893027
211140180
313674506
81080861
32738261
161640246
613399684
650162882
1000000000
418697044
781758017
82240015
639465748
850732801
42015257
716610386
160908012
538795340
860958623
537922203
222298924
249096939
351336610
380303154
711530795
745124834
905737319
681525210
189002411
987884322
934143119
333576027
366238037
364314092
369445161
649062722
993884761
230212971
475952172
735621598
363791787
850969701
561876528
31640327
438930901
842543545
519680229
241551587
931899266
637908037
963490439
809579509
762147729
94470146
169885753
810014490
728045631
765538860
810016240
378182394
389155529
106526931
624178264
829745333
932319889
704584209
980243716
16403732
108755010
644456780
580955305
330968308
891311282
509396087
218417953
62204837
315721711
658472868
12213670
955879683
744045052
734590653
43916794
860779588
408015558
423477882
499898133
56293922
2843097
585730698
889570633
477421086
801736020
980497660
47287823
186320038
338891399
373934652
19700893
275878023
755065959
663064577
485629954
934913834
99038687
467214584
460231593
615216148
2
490405569
204460059
447457955
324842588
642911210
577584896
412513408
157608623
602136101
68963176
233619680
131485451
728912012
290771236
441558329
119401793
467281913
344141436
977366143
513989551
911493404
538082260
833584742
385315147
82909202
313028263
987654321
165067437
187973407
932832426
330932294
123456789
941471389
628218140
248910252
310956650
18631697
668596448
65754259
3
948172009
595556929
155915683
349761151
204207026
872855604
483460807
334793608
717918807
367743505
370200600
987654321
31272853
976871683
385288944
405386904
384208592
901552268
390020621
528647809
570450803
926859060
455453346
1000000000
850491015
358469712
239735303
575081027
530241072
123456789
100472281
931524490
288444570
207180860
726621597
692362510
114100895
207270603
37066163
500205361
284905714
53093871
686764340
724442162
523463518
893502785
974965390
912169332
841484523
35012198
886320482
325539696
124790949
592220289
452377743
143970296
237874200
627116065
155203477
798523112