input9.txt

11
1
33
5
20
31
49
26
3
35
25
39
29
28
23
44
19
4
21
2
7
41
10
32
14
68
6
11
8
18
27
20
71
13
9
16
73
52
34
25
79
15
12
17
113
94
19
24
21
22
114
31
23
26
28
29
32
47
27
39
33
80
35
38
34
36
127
40
41
227
42
43
45
44
48
54
70
71
65
55
110
60
72
74
114
77
69
90
75
187
78
100
81
83
85
86
118
93
92
102
115
120
127
175
129
160
132
144
169
147
252
150
153
156
179
178
164
166
168
185
204
208
222
194
284
235
276
256
261
273
330
297
291
447
300
303
306
378
320
332
334
374
351
485
379
398
455
478
634
491
647
517
553
896
977
750
588
591
606
603
623
626
652
654
685
829
725
1132
777
1084
946
969
995
1008
1120
1123
1070
1707
1722
1431
1273
1179
1217
1876
1857
1249
1337
1306
1339
1502
1554
1671
1785
2625
1964
2319
2039
2901
2078
2190
3215
2886
2704
2396
4375
3149
2428
2466
2555
2588
2645
2643
2808
2841
3456
3225
4358
3749
4951
4229
4435
4117
4778
5363
5681
4824
5100
7333
5274
12433
5016
5288
5021
6304
7664
5451
5484
7759
9386
6681
9138
7978
7866
8552
8664
10500
8895
9602
9840
14426
9845
10037
19175
10290
14346
11697
10309
10472
10935
12165
12132
14036
19447
14547
17818
15844
16418
28111
22202
27420
18497
18735
19442
20154
26134
19882
20327
24837
20762
24655
20781
21244
27353
45850
24297
44991
28583
32262
34429
34236
46016
35153
38617
37232
39741
37939
38177
39596
40036
59183
66612
41089
45078
41543
49827
78278
63736
68665
78112
75849
73574
79482
66498
108406
69389
119821
72385
78321
75171
81579
77535
98779
79632
85114
82632
122613
116260
86621
133125
147501
156390
130234
177795
135887
138883
151109
144560
141669
159006
141774
147556
157167
200934
152706
183893
209866
167746
212866
219746
228395
268966
202881
481832
410635
283443
266121
269117
274770
280447
354535
286229
344655
289225
535238
637978
300262
1048613
320452
907095
351639
370627
436712
415747
644917
431276
469002
492106
540891
543887
549564
751728
786374
736974
846641
836761
575454
589487
609677
1015544
875716
620714
946081
672091
1507650
722266
801903
847023
1566795
900278
1292805
961108
1032997
1090455
1093451
1125018
1583997
1164941
1210201
1185131
1196168
1199164
2085917
1774618
1342980
1714165
1868259
1705088
2540350
2025296
1524169
1834900
2783161
1861386
1933275
2433435
1994105
2928351
2183906
2350072
2324182
4307330
2553181
4639098
3575551
6332626
3392428
3048068
2867149
4716436
3229257
3359069
3549465
3385555
5733371
3457444
3696286
3794661
3855491
5579329
6633203
4178011
4674254
5398140
6778722
6961106
5420330
5601249
5915217
6096406
6252704
8782366
6226218
6563435
6588326
6614812
7081841
6842999
7972672
7635455
7153730
13411925
7650152
8033502
8852265
11262580
9576151
10072394
13932452
11021579
11335547
11516466
11697655
12011623
13696653
19803945
12789653
12841030
13151761
13431325
17950359
13924840
13996729
15126402
19166618
31501600
17226303
15683654
19731157
21588860
43513223
23997234
21093973
22719234
28247882
23033202
25513195
24487308
30922956
25630683
25941414
35513700
21806024
37272514
27356165
32909957
75014823
29123131
45091207
34850272
41713611
35414811
76014163
40825130
42682833
42899997
43813207
44525258
52156333
44839226
46293332
60928006
66766544
47436707
47747438
89364484
49162189
69553462
104039058
60266122
73648389
70836742
63973403
70265083
127694550
112422455
76239941
95455521
83507963
87208091
88652433
88338465
105767232
91132558
92275933
95184145
96909627
107702829
151398680
109428311
187547021
113135592
141101825
124239525
130531205
134238486
153773046
217341766
146505024
159747904
194419665
163448032
170716054
222890919
175546556
231942354
179471023
186316703
198835387
187460078
267625681
204612456
272883496
222563903
233667836
472238137
316648381
254770730
258478011
264769691
386338951
309953056
306252928
334164086
335294460
378306410
338994588
346262610
361863259
355017579
402034926
365787726
373776781
487333594
392072534
427176359
438280292
568431067
456231739
488438566
513248741
519540421
523247702
611032301
643076101
616205984
640417014
848304273
669458546
674289048
712771369
685257198
701280189
716880838
1036496443
1096648753
765849315
800953140
915614925
894512031
865456651
926718858
1081679808
1798560646
1007978987
1042788123
1130572722
1134280003
1227238285
1256622998
1749267812
1309875560
1391169886
1755968856
1359546246
1386537387
1402138036
2230928756
1482730153
1666409791
1566802455
2361518288
3055183644
1958403048
2286265104
2658761034
2409449011
2142258990
4189331804
2050767110
4325170825
2440448282
2390903001
2483861283
2566498558
2876678015
3158106892
2842276399
2746083633
2761684282
2788675423
3624989143
3957705456
4812451392
3624812839
3617569565
4009170158
4524901606
5251725410
4337032214
4533161991
4193026100
6065261121
4441670111
4924309565
4831351283
4874764284
7008168669
5050359841
5312582191
5507767915
5534759056
10459068621
5550359705
7634159301
6406244988
7242558708
9706115567
7242382404
8534071764
7954601779
10059660662
8870194205
8530058314
8634696211
8726188091
9024377383
15040941199
9925124125
9755660848
9881711124
10187346475
10820350106
10362942032
10847341247
14080418019
15610020367
15196984183
13184519006
19680784973
13648627392
16112752913
23573751517
15772440718
16484660093
16824795984
18893000346
17164754525
19943007323
17750565474
22940179854
20729052371
38573785319
20244653156
21183292138
25559926215
29255942378
21210283279
23547461038
24031860253
53770769502
30935084480
29761380305
26833146398
29421068110
30133287485
31885193631
36982723997
33523006192
33309456077
33989550509
37409407681
34915319999
37693572797
46972040107
40973705527
41427945294
64975406332
42393575417
44730753176
44757744317
47579321291
64244540557
50380607436
50865006651
56254214508
62944074302
78837352975
56966433883
70972274506
97227920035
65194649708
70292180074
66832462269
83821520711
68904870508
84988728972
72608892796
78667278324
82401650821
83367280944
86185689611
93258582068
115049924391
89488497493
92337065608
103833535799
101245614087
151276171120
107119221159
121448864216
122161083591
127258613957
123798896152
231092149756
132027111977
134099520216
137124642343
150199743213
254033279012
141513763304
207149812563
155010543617
161068929145
165768931765
169552970555
372918744328
273540875281
249419697548
190734111580
193582679695
222694478303
253475976193
284299263429
311066733859
268772377261
257898416368
251057510109
255826008129
419802210777
325609791672
271224162559
292135185960
291713506517
332247874884
527929287945
420610480664
360287082135
565254381798
413428589883
363135650250
384316791275
416277157998
464806842254
444210087773
514829664263
555523425988
504533486302
508955926477
583848692477
670859720886
527050170688
506883518238
616113090264
709926582947
562937669076
563359348519
623961381401
981531539796
887771300872
723422732385
925233084475
744603873410
779412808248
1704645892723
807345738023
800593949273
920810644300
909016930027
1251487391648
1011417004540
1013489412779
1089987839764
1015839444715
1216810101185
1544772025701
1489339391195
1069821187314
1240074471665
2686177432519
1347384113786
1549194465876
1368565254811
1468026605795
1580006757521
1524016681658
1820835150802
2019487279913
1586758546271
1607939687296
2058833129671
2289933340468
1829827574327
2101404844304
3109475119677
2623779132011
2029328857494
2537847793109
2085660632029
2286631288499
2309895658979
2417205301100
2438386442125
2820081229186
2715949368597
2815410719581
2892581936469
2836591860606
2992043287453
3110775227929
4921910793963
3194698233567
3437767261623
3416586120598
3693600319325
5516361068480
3859156431821
4130733701798
4114989489523
4315960145993
4467715299619
4339224516473
4372291920528
6611284354165
4596526947478
4727100960079
6513681548511
5608531305066
6408629408051
6010108953148
9930267669109
9046298566689
8032686021892
8503025622326
6305473461496
6632465495190
6854353382221
7110186439923
7275742552419
7552756751146
7974145921344
7989890133619
8582704789142
8454214005996
11868716897139
12418738361199
8711516437001
9099392880607
12523790501659
11032574421575
10335632265145
11618640258214
16444104139615
12315582414644
13999999086767
19169935796865
12937938956686
13159826843717
13415659901419
13486818877411
20597005317334
13964539822144
14385928992342
14828499303565
15526902672490
20392884282543
16572594922761
17036918795138
27486817964178
17810909317608
20718033138821
25748435232139
31810908404375
21368206686720
33169934883632
25618639344981
24556579214900
35546532442386
52043397179078
26097765800403
26353598858105
46986846031701
29912831664832
26902478778830
28315318180976
28350468814486
32639408621173
51716405145384
30355401976055
32099497595251
33609513717899
44923063737247
54448234614889
38528942456429
52650914010969
42086239825541
83527313549759
45924785901620
47465972487123
50175218559881
50910178073005
50654345015303
52451364658508
53000244579233
53256077636935
54668917039081
55252947593316
60989877435659
55217796959806
70401558006517
70628440051680