1000
656260157
178514052
960675948
919845297
232333649
528042534
433195506
637731136
361253191
163898928
211095918
598366612
501871974
476332248
291104570
721353365
246368893
283987672
625833405
358722019
46067977
579845403
963371832
447594508
41990191
679351817
238417968
63677526
347735607
638061042
868343317
804120594
39404192
783607846
754482854
863149124
541210143
228538151
233052924
509098268
624377562
815844397
589616423
379363222
105436452
274902622
910499911
728722589
467592344
735409088
341427906
636786596
191380315
752351080
18640439
640280019
265043173
836322285
206919891
986417559
216704858
2
680511479
927659333
636897466
1000000000
597392940
562823111
902241189
164308574
885782067
965576723
492171474
366316269
820927751
782676415
952575246
64892525
845225084
840582215
23508560
28051852
218040055
649125500
7134102
979352641
584458219
628245942
191206091
58849180
712915316
721716771
253557594
308291891
366576815
210213758
664650112
683125645
989615653
606980135
31013865
241563844
485105620
969283185
897748878
608236511
375631175
217620667
228627414
952798465
542377478
828099996
718374435
701692147
807547927
194789956
619466916
968081789
372810820
766449314
906600673
762026810
867553170
881992367
277140596
251585979
639019915
858313928
62038344
103785695
601368398
955484649
55968803
300019626
671423214
185551062
291939616
867314793
682592355
598772805
558660871
901374018
265357023
548884819
328049258
735109009
19950868
333288884
927978506
688472794
395728270
393134025
309786544
773950247
746035151
327009191
878248684
523706162
684138327
235884396
312669790
633620098
794073117
175439149
752302281
133397767
759668592
582382323
884027411
447852549
364172667
457579156
797627215
52249441
122924884
66729493
26678307
18494198
862590047
219202528
920829910
75347393
102009969
619892563
166421474
811555133
372464870
135029312
625275973
897870464
242502165
707945582
464573943
585958852
218018284
153195209
274935911
435078683
205051830
688116432
810774366
121383930
347748777
318792633
463405428
996525893
13235214
576525926
784107661
115339719
713328836
848242123
586722803
408103849
935856766
955315863
777998198
873653465
375891633
375558865
305857846
321634783
215062752
462452749
27315391
560649344
801314890
102562628
246233733
671814914
512023396
587448192
987654321
556263541
40170574
977213622
189728302
739094739
953793999
134027072
578092888
896037087
2755494
245720866
123456789
713948127
390597477
26640921
502584264
828291592
928411250
64906788
204982222
440478847
103778148
199936741
867337824
11326153
907789337
81602835
325468771
551460861
471604977
222905375
935819337
337697153
142183735
193860090
213589555
79825770
754634308
105670626
334322344
681743131
108532245
51442958
368779554
221095926
27461374
100871400
194446065
326343214
987654321
989284329
366902603
778219012
739198661
958665187
319734849
996318075
893574038
380169167
634041463
47586166
236554386
329417371
313032917
378329104
750025098
887241593
571138788
201264949
888255810
764999253
925398149
274849846
53544444
150564260
720835039
251645841
372668773
679911860
647806446
264862878
398775443
101669391
469281602
263348600
478138107
278960833
701940743
29896632
933818097
220728414
358567230
381002384
737548873
789510950
371935611
124502555
346975907
602069204
720481511
265551376
754976766
420261367
406439966
990289058
984408053
169438419
501762437
897708083
53367312
117667482
274764431
457340649
899119699
957015917
612147986
749857882
52440486
280260307
935382278
712046237
722482368
363119617
317609216
134020795
603545790
242813507
106134435
541405549
118303516
302688633
881860729
573036980
468144474
1
165543010
555587371
775974620
1
537859421
212328949
770383860
286248078
926790959
420920200
648514411
387480736
276182229
473207470
369560
128677737
817310819
384560514
177954370
538664251
644669091
534007464
151649078
3
56416082
863005060
197370844
249725594
508670837
668907385
563903945
322769756
831130392
168240182
363734269
795779500
201740159
430916663
408150870
574121227
392962720
633181880
363994714
897232129
832422563
746239914
504187894
711597064
152083346
2
653476320
666007809
57717807
486410387
184293176
980736469
492881158
843729392
969414014
832787803
989930824
60579466
813232036
550823887
840122325
843080219
551835022
235097234
666319996
586694470
409630187
839503685
979305551
82105095
184440910
972837285
179564507
596256139
793382229
911177848
830421773
224212265
966828156
800909843
794888803
113870240
686567285
39136845
285200265
698888136
164024024
479636858
1
366783845
562565867
449647870
228072042
275528556
884314473
784317574
50925079
485781891
1000000000
380415151
189879326
914984156
318410141
3
936048924
610265809
838042830
371591308
329477625
241897084
665733280
308171052
879667554
932465897
474241807
709035283
388751696
1000000000
741351686
249543166
27958271
658852641
670472832
800928559
22865604
156352310
317882245
209787420
290271720
918090192
700310182
570019538
362446637
467693681
118024676
304049066
919038751
409321385
96316277
2842059
960047543
176295222
61685352
46839118
774511818
565572679
876089994
973961356
992572830
87262048
653339450
224523433
9006908
329052227
520967109
72859798
1
465735156
703140377
123456789
963821727
982774445
490562636
162435205
789701904
415349311
991981115
239733077
1
959347578
90343330
766588325
64820333
13288279
101835441
242318720
69111889
155552701
361185281
945343253
358968002
224218807
555072944
26400728
825605039
577564371
999999937
986295284
470346325
866366716
444194454
454342098
862671440
611379425
417620722
717361044
590246329
512953940
791043547
270633001
825115405
36399315
363377162
48853616
740692991
746104221
12484269
529654522
868438501
847944249
960006188
982744221
659512375
669607351
10120856
648852099
10104796
907861408
491325989
667964918
484422448
770113022
849605560
638439901
200243823
151079163
123456789
193138023
855499791
567730386
262441031
680426514
954243223
88199232
533834638
921657661
626883255
250597200
613934190
852920996
302009903
926588802
968030533
915014572
397699953
989391035
224104692
599743579
97991992
312081624
345517061
752553492
604225093
604453616
246559997
949174697
415388837
806301117
916792108
200327167
251777405
131451768
727786117
872363668
36604300
978575796
21642896
462845688
614564593
596897668
99967294
144068238
797448657
580187574
501001641
431222554
782770067
763206104
355993660
999999937
322630095
204358582
717591052
863379429
292997054
129955862
720926887
334925070
467847463
248847782
385148010
696282790
327810668
568729443
245130109
633863323
672288537
120951234
599087946
979380068
640191364
351460432
121830061
299034972
719020595
13111887
241557785
593042946
133962289
123456789
684741138
257320478
456183567
57037035
985315603
470540361
120528998
15478983
701213544
171759846
630506790
542169012
241281999
691967082
282535084
585147985
445426256
658695192
756769120
9295253
920803174
921049467
228853152
899806441
561825602
138593621
66484458
537469853
542542679
123456789
659982550
525767209
674200009
694290181
342234710
313278901
218839486
189671691
405014601
414605914
982878066
617620766
295390546
43342847
519096317
787947798
298887458
276361406
517144692
123456789
382579295
183033217
905678096
553724941
553979728
923389306
232080527
350043459
427377873
416780168
386450962
969914672
176305466
184383807
322734480
626227685
622358587
53188981
742038031
292002773
27391351
344989979
866203834
356774845
321650526
917627137
847319846
942276035
20812453
729702139
336050778
342449406
190520758
101850988
981367345
123464313
265476651
640804269
633498812
871524067
3314901
609555663
508506331
697319420
873459627
250123017
925619342
874848356
736094763
390395226
239294257
553444587
250509667
659846353
302450671
932839924
890865165
132116889
592079960
470281375
29886673
891609244
866582990
718506281
221153717
369303670
153602060
684765748
778922034
328183168
135823343
969731485
433991743
429185778
522255123
388861571
914732407
909836877
295738184
142380831
366692620
728543772
164240131
464334429
831757451
624042383
289849322
187642570
176433791
3
689824624
838573516
127179483
626227880
234230429
806666649
19884933
433389194
918652084
288365655
327470911
357879856
869343008
99267145
944681086
300584840
514269923
581534228
104599350
593874781
830333135
794202200
513079257
714034948
594920375
840103353
497510427
518482660
243988610
828304709
343409692
751690780
294046606
346936210
999999937
948192800
409462885
425936153
349695722
904332441
260696842
121844976
339389535
66520740
818938288
207191336
117075311
986813740
848874973
182166860
379339147
473431233
778590012
160032879
937084361
208566068
110875269
530466829
388252209
998348220
612083508
325868288
987654321
483770236
430718936
797319997
95641079
693887737
929988695
173340527
929426390
626252926
906993098
699233451
903920971
1000000000
488611328
935534787
16958603
596304682
311857317
831301636
473288217
953213743
993412810
165306719
919239301
85758708
821479507
289292111
75476355
113781828
701775173
677193401
428212642
497932161
13130355
499172738
635250331
918662887
990803279
793104297
483073193
991654714
437200594
454363764
586971998
331238237
884962846
244865543
809897214
822059589
131947535
620440510
647839581
25239880
290636393
949545306
600166853
819204721
888478975
250116813
331609155
371832324
92572347
321224472
145991691
905313493
277476556
204426711
384040240
463425093
179774106
945851591
723548222
500166266
548208173
766787887
969570407
330491710
398346286
810379328
338844937
764467511
886937467
511109356
265646006
126222532
138938872
40729195
174169360
122827937
80152885
969387344
7548012
978407786
929522080
240111098
335336633
444997475
189469607
384448421
547306383
527475250
108204450
952785854
888079177
613253181
435912429
420198736
589293314
15782345
863474435
288575357
317289394
745128992
422847029
398958137