input.txt

3
17
32
2
19
45
22
18
38
8
16
13
41
35
23
29
11
46
12
27
49
34
20
14
47
50
10
15
17
21
57
25
19
18
22
76
24
32
26
28
23
30
29
31
33
27
35
42
34
36
91
40
37
38
43
47
44
41
45
72
49
61
80
55
66
71
56
117
141
69
135
70
73
83
74
75
114
78
79
113
213
189
86
104
173
105
116
131
152
194
149
125
139
142
143
144
247
188
157
191
153
238
164
165
190
202
209
211
393
269
221
291
299
281
264
267
268
327
351
301
379
310
318
317
430
329
429
641
477
411
420
578
432
522
485
488
582
531
532
929
652
569
611
740
795
627
937
746
1081
759
749
1063
888
1109
963
852
917
920
1508
1677
1019
1100
1142
1143
1180
1196
1360
1942
1376
1373
1601
1495
1901
2248
1611
1637
2128
1740
1769
1772
1936
2280
2339
2515
4281
2162
2296
2553
2516
4451
2556
2733
2749
2868
3096
4334
3541
3248
3988
6613
3897
3509
3934
3705
4098
4216
7236
4458
4677
4678
4715
4812
6116
5249
5289
5305
5482
12525
5964
8612
6757
6789
10510
7443
12038
9490
8798
7639
7803
9387
8674
10117
9135
16874
9393
9527
10061
12078
10538
10594
10787
11446
17032
13407
13546
14396
16850
15082
15246
15442
22542
16313
26559
16477
17809
19673
26036
28320
30257
18920
19588
21325
21984
21132
28489
22233
24853
38461
26953
28628
29478
30688
33251
31559
44526
49845
34286
35397
53206
37397
38508
41821
41572
40052
40913
40720
42457
67136
43365
49186
93712
55581
61239
56431
58106
63939
62247
65845
66956
92551
69683
71683
111735
90603
75905
78560
80772
80965
81633
113125
160921
85822
101471
174364
115031
113687
112012
119345
128114
143019
186714
128092
132801
145516
166594
195996
152455
268347
167455
226288
194652
161737
241217
329733
187293
197834
199509
213483
225699
227043
556776
466916
453331
256206
457825
280547
278317
285256
357733
386802
654209
743081
329192
361246
349030
478381
385127
397343
424877
412992
411317
693539
504016
665674
483249
677890
614448
534523
536753
563573
558864
682599
1042113
1102767
678222
1041954
690438
710276
1071276
734157
1103430
782470
808660
1324724
1186615
894566
1151201
987265
1241463
1778216
1224961
1093387
1095617
1241795
1122437
2050455
1424595
1936679
2337412
1936520
1885900
1400714
2229060
1516627
1902047
2749319
1795925
1703226
2690491
2796613
1990183
3196639
2944689
3629774
3653655
3085800
2189004
2917341
2825309
2523151
2941222
3402527
3103940
3390897
5392710
6189740
5515800
3219853
6045162
4899865
6282439
4620567
3693409
6320265
5014313
5627091
8416840
4712155
10526956
6779209
6494837
11182304
5742650
5348460
6622380
6161075
9149102
12406300
18596040
10757317
6913262
7840420
7932008
9854484
8313976
8405564
9436059
13662436
24189392
9726468
11788166
12940284
10060615
11091110
20618363
18260048
11509535
13280468
16439570
25875629
13074337
14753682
14845270
15227238
18597737
19162527
32503368
37385164
16719540
31200332
46165804
23723051
26354805
24953706
31709473
83550968
21151725
23341083
28301575
50459501
24583872
24790003
30000008
35905407
60011048
32236864
29598952
30072508
42503610
52624947
70749676
41303412
55026214
41673246
44874776
44492808
77111640
45735597
48131086
52940035
82697455
45941728
47924955
59671460
49373875
54182824
104164268
62236872
71375920
61835816
62309372
70902364
83012543
82976658
85796220
86166054
103982618
86548022
89598201
93660552
160124183
144533271
124315955
132071330
93866683
95315603
97298830
264288451
132386418
103556699
147843376
181481657
124072688
124145188
132738180
133211736
153879022
169560565
168772878
171962274
172714076
176146223
180208574
183258753
271988564
189182286
191165513
218011871
192614433
226604863
228053783
316687121
277951710
331610482
227629387
248217876
256810868
257284424
256883368
265949916
429246698
322651900
338333443
340735152
344676350
257342611
356354797
375873186
372441039
410626304
380347799
637690410
419219296
420243820
454234250
455683170
475847263
484440255
484971998
484512755
505028744
513694236
514167792
523292527
579994511
854902944
713025781
595676054
598077763
602018961
752788838
1208472008
969484753
856881294
829845600
799567095
874478070
875926990
909917420
1343539836
931530433
960287518
969412253
1218054525
1397770597
1018722980
1027862028
1094162303
1474004753
1540282029
1686726894
1512592876
1193753817
1200096724
2118389428
1552355933
1629412695
1656448389
1674045165
1675494085
1709484515
1750405060
2312216828
1879329673
1891817951
1900942686
2509694282
2046585008
2112885283
2122024331
2692768145
2287916120
2294259027
2393850541
3227008923
3246681732
3186638041
4240413759
2752452657
3181768628
3208804322
3338897210
3330493554
5078455992
4506735824
3459889575
3792760637
3771147624
3938402959
4903544823
4013827969
4622579565
4159470291
4234909614
6520665838
4987027172
4582175147
8085313451
5146303198
7733744747
8446916747
6547701532
5961256979
14967582585
7123254191
7231037199
6669390764
6790383129
8006057238
7252650212
16091370689
7563908261
8596003116
13029091894
8173298260
15569965499
8394379905
8741645438
10948284151
9569202319
13433943919
11107560177
11694004730
13338084661
12508958511
12630647743
12751640108
23964345404
13459773893
19113617415
14796440367
20435650168
14043033341
16159911377
14816558473
20194556004
15737206521
24991317492
16567678165
18310847757
17136025343
19342664056
25924118650
28790559120
20676762496
22801564907
23616518688
29887665451
25260598619
25139606254
25382287851
26211414001
27502807234
29612998840
28859591814
28839473708
29780239862
30202944718
35910342221
30553764994
64769934035
36478689399
33703703508
37812787839
35446873100
42518313194
40019426552
43478327403
44293281184
45816368750
46418083595
48756124942
50400204873
55162527713
93629525849
59983184580
66672379653
58472590654
57699065522
73132754892
76222016702
75596608612
60756709712
82459828450
67032454393
117426036076
70182392907
149132208103
95430057680
75466299652
88775551494
104288959404
87771608587
90109649934
94572493692
121884383247
99156329815
105562732586
112861593235
116171656176
154443988240
133938890306
118455775234
124731519915
142629063005
127789164105
156186767392
136223009364
181616158265
137214847300
186927938402
231653067044
163237908239
165575949586
179755259056
198861453096
177881258521
182344102279
239501622892
193728823507
217612105049
204719062401
218424325821
246244939339
243187295149
252394665540
261728054411
261946367215
260954529279
264012173469
301798958950
273437856664
356966731746
494181579046
398179584877
350165846641
419256881948
567777951690
343457208107
357636517577
360225360800
371610082028
680211411227
398447885908
411340928556
422331167450
466665429616
461611620970
504915349560
495581960689
513349194819
619364571988
522900896494
700246844858
537450030133
710391207441
633663217464
809788814464
693623054748
715067290135
701093725684
839039168796
876525431588
1030705500544
793941249478
1071856926886
782951010584
820779053358
860059506878
833672096006
883942788420
962247390305
974960815789
1000497310249
1114946532677
1535846343493
1060350926627
1156564113958
1237696874991
1231073084881
1327286272212
1527295150754
1484044736268
1534765821690
1659818222154
1495034975162
1576892260062
1603730063942
1614720302836
1616623106590
1643010517462
1654451149364
2064745180887
1693731602884
1717614884426
1858903604209
1937208206094
2726108060043
2845793387717
3221309294845
2216915040585
4462416494307
4459006169836
3174905081085
2558359357093
2811331008480
3018810557958
3228497424574
3831635343421
3071927235224
3353938579371
3191612562898
3308451905720
3231343409426
3310354709474
3654823090520
3348182752248
3411346487310
3552635207093
5090247013635
3796111810303
5438224335430
7003005842768
5906542109341
4775274397678
5028246049065
6193715639043
6963981694403
6247307982532
5369690365573
5830141566438
9058638991012
6624562442317
6263539798122
6303270644650
6765285066681
6965177799994
6541698118900
6579526161674
12077449548970
8327909604771
6759529239558
9317888596651
10118493062700
8571386207981
16283066396645
10968990036721
13762535082326
9803520446743
14834926006103
10397936414638
25803916042824
11199831932011
11949216527247
13589740242311
19296899641492
14631180249421
17741530050911
13068555711331
12844968763550
19828084950889
17363114214632
13121224280574
34663010956992
15087438844329
16878022302258
15330915447539
19540376244702
18374906654724
18969322622619
20201456861381
20772510483464
23466492125969
22872076158074
53037917611716
23519160695212
23149048459258
37942986912292
24794185290797
61462147607504
44334561535499
25966193044124
25913524474881
34300238070158
35288895705710
28208663124903
28452139728113
29999246582832
41297108491663
61092035371550
39170779484000
33705822102263
37344229277343
54365664202994
49432685170093
40973967344845
67942233495124
46021124617332
46391236853286
51879717519005
60266431114282
47943233750055
114333470348410
50707709765678
54122187599784
54174856169027
71934649092213
55912771057713
56660802853016
58207909707735
58451386310945
77942480332887
63705068685095
74679789447108
87365204198131
72876601586263
71050051379606
97900842136337
139876882587337
96728834383010
91681677110523
92412361470618
93964358367387
94334470603341
123814366611218
110087627226740
98650943515733
104829897365462
104882565934705
108297043768811