1000
438081167
646460119
981237692
86594899
634558108
708636814
169066678
686387483
843718451
668771913
773904183
400276089
401065657
153316171
809471397
300335200
455810305
526272809
717437796
906470550
577879709
941237016
489041728
300397128
508956490
512105206
474377898
855751286
204017219
301251998
286764053
125110804
977840871
311662759
68063748
544288983
476946275
950251599
605378563
789939763
829923809
74582807
187625787
494815674
562064877
674185382
951893558
25816088
479606692
390365766
606297005
766049109
980204348
130067310
805370862
1000000000
374196069
925337484
745726640
862463934
394767889
162457308
352700188
108869949
810735577
821381150
791826287
379165149
537234766
116016128
395721712
730623179
48590385
621141101
857469823
948372672
366655189
492577622
594630704
29429492
717322824
952647503
55079050
957100571
460652070
275344338
135725163
3272611
164007362
165702911
42685483
467739057
352881890
543234342
986054623
53609905
592433482
123456789
488559240
808947447
847060528
35548206
305378054
161271068
36298325
55497321
700136571
157984281
659357698
860173793
148449921
393370176
422940044
979668051
251644995
318083009
217102499
251784891
933384642
999999937
400965386
119919107
559475883
111295898
723634863
801178355
674752056
138418241
800632213
803655205
505463898
568625692
700497485
500593619
106464050
551722557
583231377
999999937
847018013
179666236
202723967
165036836
91231463
243066537
2704904
307092179
508916695
544755550
140668905
402663860
622053129
663230650
115176329
942366419
921362260
352412040
557975537
244885042
678078488
588978206
557735567
714486718
637627174
823646359
685250743
673881798
808090399
681587096
641420270
830313981
987654321
116953144
405766088
488506717
645728779
321145114
1
3
310245675
272409710
361256215
119949198
758970598
128895573
817652959
973754481
367485570
454913531
645586933
801835916
273010170
682961996
637135180
424024475
141568333
881057734
264204557
169058646
599305723
693647309
977071842
389992087
175603579
145411638
594450821
846822020
648011160
747554747
652416208
658778269
235246549
835711385
495622122
855080352
1688111
292354773
450268822
665348144
971482130
300160574
285814885
615038415
862983015
733373526
914425880
695663792
306637776
159401227
650143641
149116505
321482535
967982311
829617654
323816668
725253883
520922623
87047487
999999937
120680403
337472802
204299524
829048380
472560189
609873072
727189804
819749532
74919693
6752893
489667171
163345832
512842840
136276304
601886280
534503463
369993923
999986003
3
258965123
929046272
436950319
575570883
690690801
34415052
490515550
787192745
619351463
54578691
695149522
439296736
483757410
745502470
1
734773226
450324210
827096025
552868271
768306720
498862505
891739505
952877839
1000000000
1000000000
778265440
206227340
243152404
514627410
642604984
816424311
174149681
393944848
889490418
730497423
714171648
805782706
635250913
305150944
988819085
939604526
452749995
194573495
1000000000
252922297
767598837
569557987
648998105
1
454604562
601434433
153619335
525857384
232963270
810340210
31220967
3229379
622009055
557921186
953917355
642373245
449107750
542395271
822860661
363898945
545299449
133064582
541774789
506337322
323269284
609852021
802391272
623519659
409474738
3
17972678
284875937
261545230
616145891
1000000000
694420305
972522263
389523165
841631506
573388509
826746034
419537837
616466611
35519159
564766949
939149854
41826897
997144591
501781774
916865513
704895738
78413576
842248294
92177014
794019388
3
789959958
855607329
546738434
503652063
602417570
316448280
427174740
747975615
42716809
515412074
699927679
774087817
599806003
683819549
208576721
157708313
780487693
459590108
444868352
512644938
817520484
847218424
898773842
64033778
553950558
136282179
327246920
68768226
236328840
322040269
102550109
673726241
718542764
541128657
255753362
508180335
191800811
936235020
169143229
81388575
417157050
933005885
428756430
253292993
921320385
919716468
351614769
432409756
199236812
971970502
956643924
144675518
783641908
286928527
503630241
18473452
347146897
984481428
737668632
683838976
391662674
756974242
794477095
338071071
938031939
143242646
793299044
832900363
315322851
440967448
851138677
356044166
179332895
365509065
814264844
172457370
550635593
301181173
346934268
15126843
741669533
370720816
533598602
882509703
528739440
572115199
250529256
211061886
404239085
364416218
311240467
203957265
115885244
416221349
564479560
110486380
102007392
416138507
430746170
239632228
125880134
513752104
454192725
1
971664420
714295952
803559426
604562638
855261809
660786293
463106596
515343741
378511862
301177351
415614098
176937936
941788533
25782255
215052345
575066013
795051534
734601993
795899310
62314302
1
187764753
123859208
506991729
547033171
605164913
894096681
904658588
679359045
892566672
224150257
121544376
801623808
599508456
286636008
658820706
867075042
285711879
864222854
810964243
596739459
3
402042325
633975573
789329300
780612633
807256109
465257985
784005349
252205949
832728853
299683038
331296004
262081263
193336209
41191420
619884067
50371401
931823968
279341537
400963793
610854527
959597990
808480511
761473976
364770701
520894816
466257679
48910798
730052568
367623924
800187614
501943961
231113093
524480285
141169964
339414901
52094741
855301096
39495003
20835454
297518919
196121744
834990701
3
529274782
409596977
37559438
686561924
770448162
55979302
694233951
887502196
362965216
374908483
621231148
627994029
631477381
778264095
130215837
458169355
21812898
451949033
856581192
991183983
882073739
145329080
584795462
787660849
216243997
169953482
412277633
437333901
250858296
650117304
979576124
385737310
320790078
722446743
717007220
97121483
297708956
272115199
210062339
22547454
446600180
987654321
548707307
283677216
509973912
559409903
272468589
469069554
340578913
488649776
489819096
952940386
408678979
840837126
985869965
413380310
715339707
895735953
615403902
462868676
77213057
278024167
495818293
629444594
753463078
748552954
999999937
998270362
731487938
809601237
677161288
858248777
228235474
764446065
213877101
171869605
751143785
688971048
480674854
318952922
874286199
313774264
118964392
972265541
211841711
755724393
379648150
337012922
772907137
133964209
159370629
17060004
44124054
972109294
377433813
109727823
952412451
267862325
320069404
170401062
914850898
23544245
235794965
818574743
669727324
2
819196773
493940655
23466684
228470986
386903933
421467996
350772097
332257192
617985841
925622583
917798642
665924612
18019451
922041306
673791540
672403321
981750482
106631007
364843629
586582555
862274087
856452623
820235765
254865032
78244503
21817907
214586093
419450144
589083562
782805491
912543457
821622662
775975531
762102885
737009638
735883449
214539110
199920226
940119758
541459992
953192453
936923785
3
1
42229075
138190665
683316403
133092985
246419968
466033945
436584390
440663545
197156425
994331601
734456567
206339858
675454825
316697452
242348198
137123475
252715848
108489481
452052434
888611460
358634897
142272234
903562593
764965380
620659382
112016710
664144396
80232302
719210088
847081528
20217670
69456124
747401877
130351613
399179854
153259859
298792310
213901193
427811546
613173538
64219718
560620650
757780483
865702336
296214331
851632659
228345526
990787052
794892537
517627104
180049393
339657480
759702631
537563535
205558830
195239196
338355313
9402608
949090413
31936030
785465676
539399360
900873203
978376733
352912830
790727227
458184332
63354922
327609072
738374791
551990883
889742510
1
121397390
298836490
947629104
317871340
113311691
871448318
583810623
114978827
178609398
1039966
705285869
478322839
878474938
36393425
815603994
602433985
224794705
935331533
345716150
643775184
482595928
841077616
691174448
223071909
582395943
737454134
84261990
782870314
456287125
929302849
757942976
35388095
336846501
79029159
227357226
283366711
68015829
474035866
831986568
466292120
288132480
397910107
719566144
820896551
924078819
56427632
787233048
716262951
78584314
211256776
17479604
464507561
536094457
970065042
461316124
663173567
148976345
338329285
50202406
339287560
46574591
80171544
747692469
625236333
476609446
255494559
804663957
51251620
654626106
648746048
771525303
463407011
249504400
846505209
970304109
123456789
420127086
127276312
891860403
973972763
982528796
528963843
659163439
290092546
816180255
459368902
592861502
123595693
804265055
792726694
835638330
794870209
262627847
579190756
468335924
2874540
221635647
554444306
620338979
354856656
284455638
801227436
699007454
990326118
671798233
192930529
106645797
152814521
59157909
221933713
499799197
276454555
818466606
374180492
49430370
32549807
78046102
329096810
995969869
699823697
380770111
992394688
973817308
418912062
111711639
732783155
309363859
883386085
619464007
745036074
156225517
956381181
301710031
374323445
326401280
139666964
452096094
33344770
602731510
630135017
194249396
29402022
597076595
229553374
696503830
600435215
192584326
3
16338705
387089881
934459094
119714463
303985812
864128957
437046517
194138822
309514532
108724467
377510110
417698900
414463656
601230534
288340448
320217547
24299361
61750304
616978139
314345710
172617750
272459166
480803738
447635946
335869610
580983190
867490561
994453530
345696918
123456789
447895933
817149898
198708635
48868729
636485592
539959971
983658698
67886642
438156566
812063646
612336672
1
748129472
864990493
2
338673302
275586402
443685888
805110383
170225943
522644527
680075979
626300312
872799435
944260937
778274300
214819382
728215729
225450203
1
278881622
961239372
403624073
734135036
995175547
474133538
637222482
591964767
852981250
867959405
233277563
401529935
100505423
326098749
772179852
176838507
156504554
387061205
872904948
412941167
207223330
875072517