1000
451705200
980045939
908966844
9503657
182173342
974692943
904585571
212547944
713605740
123456789
27448341
111753984
464482888
843443568
344952872
444082744
485110794
282027214
576951972
320946040
384403088
3
122156964
619861696
461685113
749810162
457385862
216895662
65640314
549907885
79044998
452257668
690737617
403821597
94950449
74850260
495441403
341640808
488850074
884443638
658535793
330245965
406050573
484005235
596945173
536462278
531736458
319590318
85903317
891761858
658559153
344667157
983907780
615752411
717821404
260200070
345705029
3
68112993
360620094
164789311
401481057
101410456
604074530
423434261
795415016
30816081
534508068
616247171
769032327
791458882
14073850
231997929
683852834
829170568
921497219
675484645
853851428
380634229
685146009
618695808
23937886
826884868
781431917
515770683
988673480
262374606
999999937
888795451
910100649
817897961
486418873
475710241
649127525
703770641
780439804
452849722
335038863
689305671
19324166
618838545
398437496
486408152
147910195
702246544
383899992
172722694
651479839
540619909
445905393
65779896
356757675
95467788
221532427
400283962
391696027
58919200
869709958
1000000000
99060315
695044168
818564076
623114238
444156372
631298507
744052485
829363456
226666230
50232843
566744647
158844819
221829342
957093596
165892277
502105702
667960031
132266176
926622605
600698068
776202661
673734328
598655496
291371535
934543704
536678226
344165272
872687184
290751294
730689388
145321517
135522824
677091414
399870698
87063073
204667660
744216914
92815908
519922916
582484788
882589181
948657895
443592968
386736839
25579448
353012105
587269142
637017327
874706701
831451973
364044531
123456789
384784496
854939696
854443586
879829603
370759257
551577353
16804695
104791262
847585651
615304808
272313939
596118805
387094226
863265087
242744878
375171530
902850562
439727492
368742122
20602121
39447155
536489883
575921248
123456789
681676055
985564001
946064048
456808936
169537125
646616529
428629272
646003015
628928757
684340081
914409141
700168774
303835141
16563564
644139774
323725033
859444491
205464620
287788979
591040654
18854312
269247930
853098355
214354132
803728400
806542997
64829910
749331684
716355332
754139783
499519893
295930650
527423584
956819734
273830200
57271926
209348392
708505461
531208593
955208336
64506875
323568018
961423086
391621540
822661428
626985917
993037773
261654191
395402194
507322819
606846475
469710020
844417888
993580320
334306155
359395861
777742131
971770122
329166414
159372531
794463771
611708077
717837456
428219863
766968039
742361015
522732275
167358657
333471090
577066099
223145727
571285319
221168210
483726198
393954669
174055213
532370608
171517016
259173740
996366359
844446759
844520765
910933724
506155520
329340660
573003262
999379160
127919454
490683882
221300247
530344718
17174459
427957803
306138148
654023913
192151014
637952244
967995426
737687144
789353167
973279520
480380577
257820001
332703429
83199736
143729879
176692805
171165391
729087131
427456983
987654321
501826799
484412140
556568021
543117259
148388546
389591048
653418644
96399881
824475407
958207887
851078488
13504180
151937731
361213005
284807215
12684818
178572729
550916603
436111511
321397513
44577224
586058575
125057852
960916911
906234047
971322463
422237496
206629241
715004496
266736119
473585784
265465953
583296579
656772485
511960657
696612032
2
403360866
201012883
275216076
214882409
634134429
82306506
746086411
430349713
665913272
1
232026625
107799816
886217732
822069556
561617393
970691781
494952790
981018522
124406371
752741370
35280924
780126751
48969952
726345141
820426305
739079603
832896256
464723179
49609880
254458662
892392126
766341769
546601076
96206316
757516515
370730554
306180908
288647317
1
1000000000
426726729
1000000000
375354495
492574978
489089867
367223461
827345258
608685703
968170445
30509290
23014283
245200600
818297458
206843970
223469583
580276987
847350900
82989529
126258025
252441113
330499754
349416476
149070666
816115319
473604191
616551769
13560159
882551408
749085416
645537799
339014860
191518663
396211019
538569815
123456789
521274238
371942043
373413998
894696540
301577587
3
1389427
666895780
606998611
727915865
406921392
743542530
645829166
37403190
806200858
684017607
678111041
456396846
3
183601062
52568082
881587456
10738630
408299165
402927775
240438191
671734298
805612517
450888795
381012275
655007133
168077958
644295727
390208364
34082589
867477186
975664705
256444271
740556356
990564967
2
10794929
65317858
582507750
201250790
982272358
273564524
624794418
201906537
803760002
968723041
987654321
875395129
123456789
171224204
648731012
739642369
270545995
963726843
805966177
44214302
322346938
628764080
830360917
175089430
316965921
977325136
466665099
910975566
236128360
744370467
331840940
356020020
145092160
310538830
668220114
235105486
476138976
101706913
937730887
866182847
464257962
327681075
22571463
861008978
407354251
730471716
176719741
994949961
802223034
28678866
240835384
147503657
867768263
505946226
823646272
780684525
60839520
945386299
678983777
749587981
278993097
731026708
565958941
228180298
458306060
964216169
993772006
116365141
835082562
328538191
346950869
959421975
617055189
786886897
163331790
317381405
98666192
589956306
674467151
320647318
775438450
817188288
32365347
656075702
291545431
492102383
482835903
206626965
458204377
121550118
872450237
1
391206018
502791869
367482117
839701490
37456333
14743261
33227184
506683801
151671087
923770396
2492594
40022389
569378412
929546196
779946048
728853629
1000000000
435559107
323498287
508399363
26688382
491116831
391716258
987654321
908087456
568753552
821759342
358789205
617482415
963538924
423207642
534407818
51726790
561263545
445906717
39227211
508632103
187069981
261035886
1000000000
915272938
444781250
716265476
745303870
221345596
903645974
641669260
829548248
871377729
494934126
977414524
17188479
7229437
176860746
566296962
392749
262428540
608540541
131109166
257534751
922338751
926691801
500942287
86151801
397881970
53289826
223971620
425824645
244799261
818022475
181501368
159096994
251051107
568548239
616341647
69389426
663121144
443751943
893892226
849358259
949733794
94029646
498717415
239728952
159879014
137385501
18901254
922203882
382175136
984341751
96259443
927410790
456663272
497320592
387559352
425845088
854528401
1000000000
782489018
878896620
612710815
807009310
794105280
560635394
109971724
564522777
131722020
999986834
100094713
70627218
515869180
390499088
674459918
210765355
169637279
919190378
45259021
629928699
819273710
787613597
83357289
635073300
3
649520421
79890427
925913037
14589342
897644758
129219770
98350346
238869071
701900271
419268317
225515862
146659407
727500181
74316435
456453582
440138031
280717387
521896086
987654321
23219723
841636398
731624469
241573840
557039546
220722856
653763198
884861201
84982815
604734290
884593453
14408997
310069834
738085916
999999937
901622017
858306488
235789848
638912235
45255537
82203740
584682046
470691722
265701748
618862106
200076309
221255024
318066116
570564799
585922911
592370899
968286381
378888099
220002140
150735331
146368434
284579373
15211268
464797434
482053634
303086714
319641666
854913318
983918721
296937662
810352549
389184739
624675456
12786918
894092035
839159597
459762094
504929983
205078998
617853528
975876150
317007110
978930376
480964927
531168343
587463898
410281546
546163251
985502933
773281378
617778251
591324906
52051327
997220741
738929873
302931148
237682297
917765351
179835585
661203593
416796342
78698570
873745447
209430459
741019245
851332258
944459127
109032257
266205095
871072254
334706410
305944343
354424296
235925727
834799176
275146091
65045711
874158631
556582072
627812415
927835285
861252319
262255989
210617577
17952959
60312795
95274808
921328005
372708520
10388550
220160546
889609329
414743904
496400767
338577478
523351470
587002620
890766489
838988560
183566566
774806797
780427555
317579321
63916316
772673365
995573782
295545727
1
449685299
977964177
655656716
443427239
307985237
239876362
545208700
757993361
984040145
800793398
146908075
520285135
818463580
996195892
4516207
504942767
794132532
2
870139303
72732093
428289634
305860304
910109835
792806713
31009946
293559770
788451737
822781944
219872243
436880049
109991519
953589398
205101437
1
891020882
660622849
729387163
633496312
146115336
754970959
552806774
85788084
5515029
537612757
317702140
351149261
374730150
1
887595992
22489429
694848025
782874256
270721332
329681820
121334343
731946568
773253654
655625438
616319664
76280981
328172849
721301168
296438333
699499859
5094163
659975006
733879074
248307465
510586513
730868040
636078401
98557042
754779916
833779908
761047902
241825779
55757943
986483843
858776855
939980633
393763929
308158865
341638986
72985080
658315739
11023387
641220398
210790889
90708789
997821161
169476419
765612236
472900523
131169526
527040461
646421048
485232889
301331467
577313240
995484789
878470216
446110701
483059945
837100455
406351766
279739565
375335579
960633712
60724817
838564380
499797187
84705687
172124339
526039982
276491976
93276894
870134302
837937773
285820152
27062122
104499
451729090
387353529
219784741
125903072
370855594
969305254
628106700
896294784
695950549
325861523
196141179
77633830
267429295
359643920
299721760
100749880
493710988
484861376
365671406
806058965
822197494
966486115
830926898
184525786
212932819
2
733961185
246527459
440667690
126459220
660347838
978725474
410825545
789636586
723691260
587087153
714628888
281233716
156298153
600315418
628096598
138017265
159211672
974437977
587541903
361266678
484275925
858337545
636641065
634340406
169841322
682617741
542059772
294803026
769905833
429747391
848851834
989541757
894528137
63326802
991830750
31401652
581920544