input9.txt

21
32
15
49
19
30
50
40
33
45
11
42
26
10
12
5
4
1
27
17
41
43
14
29
18
6
24
16
28
7
8
31
44
9
13
30
85
11
22
10
48
70
15
19
20
17
21
25
14
23
18
26
104
37
16
24
27
28
29
31
32
44
30
46
39
33
35
34
42
36
38
47
72
40
41
43
60
45
48
49
51
55
73
59
69
62
63
65
71
67
68
89
70
74
78
160
81
83
136
90
117
130
99
115
100
106
118
152
121
161
219
184
133
142
145
146
159
164
155
168
171
217
381
252
189
633
205
199
246
221
224
239
301
254
459
275
304
323
287
291
588
392
319
326
475
388
711
394
404
695
429
420
540
526
445
692
849
1066
529
562
566
578
675
1007
970
718
723
645
865
814
792
798
823
824
1247
874
946
971
1398
1597
1174
1140
1241
1091
1128
1211
1689
1738
1363
1437
2995
1368
1443
2263
1770
1926
1951
2145
1698
1820
1845
1917
2062
2219
2574
2826
2911
2302
2339
2491
4109
3066
3175
3934
2805
2811
3141
6079
3468
3543
3518
3665
4122
4219
3737
3762
3979
5967
4558
4641
4793
8418
6424
8328
5557
8101
5616
11065
7477
6279
5952
6609
11250
11072
7762
7859
10745
7499
7716
7741
15863
14138
10510
15027
10593
10350
11173
12231
11895
15239
14041
11568
12888
23068
12561
21995
14108
25772
15215
15240
15358
15457
22581
18066
29971
20860
24783
21523
26922
33563
21918
22741
30672
23463
24129
24456
26783
30455
26669
51494
29323
29348
30573
46129
68710
30815
38926
43601
51266
53434
44989
43441
44264
60020
46374
50132
49410
47592
53452
48585
77935
60163
55992
56017
58671
59921
81839
86518
96875
96255
78407
82367
91363
87705
89253
88430
89815
94396
98717
106537
143847
142705
96177
102037
104577
115938
114663
190573
118592
186944
138328
179068
160774
166837
171620
176958
170072
261297
176135
177683
234505
184211
193113
202714
411463
219240
293621
198214
206614
271414
285429
233255
256920
302803
299102
391327
382749
327611
341692
380397
346207
347755
353818
396923
361894
631428
504669
395827
400928
404828
431469
491835
439869
463534
490175
518684
532357
556022
669303
730504
903777
710360
675366
1088379
693962
701573
1361932
715712
840797
757721
796755
800655
805756
1019556
836297
995891
1363265
1551913
1179246
1205887
1051041
1257595
1433087
1344669
1606411
1369328
1395535
1376939
1409674
1417285
1502228
1473433
1832188
2302883
1554476
1597410
1636952
2182695
2042184
1887338
2547804
2588920
3209127
2230287
2256928
2446576
2764863
4618801
2713997
2746267
4421108
2974349
3998594
3524290
2890718
3389566
4299112
3939835
3151886
4763603
4144266
3819647
4070033
3929522
4117625
6363915
5021791
4970925
4487215
5160573
5192843
5460264
6971533
5604715
5636985
7377933
5865067
7221919
7453812
7081408
6541452
7091721
7269511
7639101
8951313
9935100
10470974
7999555
8416737
8604840
9458140
9509006
12241981
15638656
15663817
17556153
11097249
15146292
14491430
18886413
15080963
23096270
16476552
14361232
24962404
15269066
14730822
32601505
16416292
20658718
16604395
17021577
17457695
26366315
18062980
30810109
38734926
30932883
25458481
29222252
26243541
25588679
28852662
29092054
51591601
29442195
30837784
29630298
39323636
29999888
32290643
38116413
33020687
33437869
33625972
34062090
43387892
43046374
62462882
55030874
51047160
54680733
51702022
54810931
58074914
55096203
71614279
64275653
58534249
59072493
59442083
77449982
98077248
105858091
87386846
65311330
66458556
66646659
67063841
67688062
85109250
98198823
160661705
102749182
118160578
105727893
106798225
106512953
150420580
165765310
212371044
154450687
172496096
117606742
125531049
126088742
131769886
131957989
132375171
333157801
132999392
227120261
133015568
190837143
250622310
183308073
263964133
212240846
208477075
212526118
223334635
213311178
224119695
243137791
329847588
243695484
249376628
259088134
249564731
251619791
339399920
263727875
264333160
436645813
357135263
266014960
442456934
580469898
414171778
391785148
395548919
420717921
425837296
421788253
435860753
644837616
492702522
467257486
486833275
493072112
493260215
498941359
501184522
513292606
515347666
603733080
748920411
530348120
623150223
752684182
657800108
1070674912
787334067
805956926
812503069
816266840
887975407
847625549
857649006
1302681733
954090761
966198845
1801716310
979905387
992201574
1596545960
1014289025
1014477128
1043640726
1045695786
2024765673
1372070634
1188148228
1280950331
1830555865
1463757034
1700478476
1593290993
1618459995
1628769909
1972106961
1705274555
1811739767
1823847851
1946104232
1920289606
2035842300
2364272208
3215005955
2006490599
2611023088
2028766153
3293769469
2233844014
2326646117
2469098559
2560218862
2651905262
2744707365
4885749276
3057048027
3211750988
3222060902
3840505920
3334044464
5421320235
5945067552
5023490755
3949055759
3866393838
7052256908
8414166111
4035256752
4240334613
9002115579
4262610167
12842621499
4794062876
11562334441
4978551379
5029317421
10923618931
5396612627
5801755392
6268799015
9823380297
6556105366
7062566822
12081574329
7200438302
8106728451
9056673043
7815449597
7901650590
9772614255
8275591365
8297866919
9064574173
8502944780
9241161546
9291927588
10007868800
19064541843
10780306771
12794000976
10425930048
13672203992
11198368019
15307166753
13469237317
19282012631
13618672188
14263005124
16573458284
15015887899
28837156098
15717100187
21434121785
16404595370
16778536145
19496234938
35213335125
27771826303
17744106326
34080429742
21206236819
24044602236
21624298067
32965472255
30245662276
23895167365
31420483269
24667605336
28634560087
27087909505
29278893023
29980105311
48712207572
30732988086
31794424044
32121695557
37240341264
51414227096
33183131515
48978063122
51824536068
38950343145
39368404393
45250839055
49840796906
103238763164
45519465432
127133930529
56462029380
48562772701
50983076870
69034765308
64328250769
71162828437
56366802528
77641160989
76190684409
67973329350
82491180319
63916119601
78318747538
70423472779
95360262338
87513115846
88791140051
84201182200
109847716201
140106804010
140518935178
96502542302
113492794782
94082238133
139458238087
177821045551
99545849571
107349879398
120695053297
120282922129
124340131878
126790275307
189841059717
131889448951
148742220317
134339592380
185668626936
154624654979
157936588625
171714298046
172992322251
326338953025
191551061598
190584780435
326563265868
347777648342
193628087704
201432117531
214777291430
453129228332
206895728969
219828771700
227632801527
240977975426
541116244455
258679724258
339327000752
266229041331
334410847253
283081812697
288964247359
312561243604
397480509404
329650886671
344706620297
363577102686
382135842033
476709900401
426724500669
395060205235
546138737828
400523816673
553539219030
455755266856
541761536955
434528530496
636038180661
468610776953
499657699684
524908765589
547643971617
555193288690
549310854028
572046060056
709806313366
723492777855
642212130275
874190409805
798261663624
708283722983
745712944719
907044607622
856279083529
980667268324
1005066120884
835052347169
1421834381422
890283797352
903139307449
1047301671301
934186230180
1403923055146
1017921630981
1024566465273
1072552737206
1096954825645
1104504142718
2428489520419
1660133761256
1418090036349
1350495853258
1387925074994
1453996667702
1506545386607
1543336070152
1601992028248
1691331430698
1738191654618
1725336144521
1824470027532
2144256496946
2278208872346
1793423104801
1975692044655
1958752695453
2006738967386
3549806172053
2042488096254
2097119202479
2460477812200
2201458968363
2454999995976
2768585889607
4185813956721
2738420928252
4497488092230
2841921742696
2960542054309
4476612582870
4479667840709
7440209895018
3562661682150
3752175800254
3617893132333
6404583424846
4635344847497
4208197935749
4848660710082
3965491662839
4001240791707
4049227063640
7803707089054
6023139494350
4298578170842
5162001022672
4970044857970
5415542050285
6807413405535
5580342670948
8843542783246
6843162534403
5802463797005
7168739990058
7180554814483
8209438727456
7528153344989
7314837482404
7370068932587
7826091068082
7966732454546
14696893335047
15494885799535
8014718726479
11777458263505
8050467855347
8347805234482
9268623028812
11467318160900
10101041967847
10132045880642
10385586908255
22338048333938
17319090884159
12423505205351
12971203787063
12645626331408
12983018611488
14349294804541
14495392296887
14684906414991
19092295745909
15281569936950
15336801387133
28319819998621
15981451181025
35073746926934
16065186581826
20438223931830
18151509823194
16398273089829
18448847202329
25394708992414
23356790695318
20233087848489
24880979205142
22809092113606
25069131536759
25406523816839
25628644942896
25616830118471
36339809306806
30560578878713
28844687101428
29180298711878
53936650117092
34429097133042
58024985813306
33785648589462
32046637762851
90276459423898
32463459671655
50495484965180
34549782913023
34847120292158
36631360938318
41805637897647
47878223650365
50475655353598
43042179962095
51989390825484
59402478707933
57115769299610
51023353935310
54461517219899
54797128830349
59740877590591
59405265980141