TEST DATA FOR `hayexp'
A Zip file of this data
is available.
Input for test 1
4 2
5
8
12
6
1 3
2 4
Output for test 1
25
26
Input for test 2
10 10
489
849
603
712
711
719
391
120
916
221
2 7
3 9
8 10
1 9
3 4
4 10
4 10
4 7
5 10
2 3
Output for test 2
3985
4172
1257
5510
1315
3790
3790
2533
3078
1452
Input for test 3
20 20
61
94
893
987
159
643
85
786
531
685
30
428
714
138
875
428
309
677
689
352
5 18
19 20
14 18
17 20
3 11
10 19
1 17
15 17
2 4
6 16
9 13
14 18
12 17
4 6
9 13
1 15
9 19
1 1
5 13
7 13
Output for test 3
6488
1041
2427
2027
4799
4973
7846
1612
1974
5343
2388
2427
2892
1789
2388
7109
5504
61
4061
3259
Input for test 4
50 20
315
708
21
753
223
686
16
497
916
546
742
671
677
237
352
368
358
876
164
22
991
552
710
695
162
542
528
448
270
241
285
44
134
218
644
660
307
569
96
738
892
372
237
89
172
501
730
480
45
709
20 40
11 34
34 38
14 26
13 25
6 31
21 45
9 13
9 23
28 31
7 11
16 34
3 25
6 10
16 38
32 42
9 50
16 49
33 43
39 41
Output for test 4
8856
10287
2398
6029
6164
12552
10596
3552
8182
1244
2717
7608
11235
2661
9788
4674
18990
14140
4867
1726
Input for test 5
100 100
728
936
606
3
687
810
360
176
356
297
103
461
960
622
23
151
950
733
107
324
234
834
545
352
823
312
781
514
151
337
977
913
591
455
966
876
901
217
884
569
737
334
823
931
828
45
47
359
766
643
666
806
739
543
468
304
858
30
652
716
865
271
786
494
101
486
47
579
922
382
454
442
773
484
848
556
425
507
79
706
355
682
462
484
983
714
368
491
845
994
364
722
987
992
290
526
197
600
434
780
16 94
6 78
27 58
77 98
40 89
31 80
2 63
12 15
52 90
68 71
39 57
34 89
13 83
1 69
18 49
19 40
37 60
89 95
60 96
32 73
52 92
51 79
85 99
73 74
47 81
3 42
35 75
66 98
41 66
46 96
20 26
66 96
3 9
54 81
24 52
43 51
52 83
99 100
60 84
89 90
13 70
5 10
36 39
44 53
9 71
32 51
20 38
41 43
66 88
21 65
21 23
8 100
20 44
26 56
2 2
70 97
4 19
45 86
22 98
6 78
64 76
5 62
6 19
1 18
35 39
62 67
19 34
7 53
4 38
19 29
74 91
9 44
44 55
33 54
11 27
28 39
28 39
25 43
8 66
77 79
43 63
26 47
16 100
24 31
38 78
18 39
20 64
43 92
41 66
2 33
17 89
19 49
45 52
11 29
7 44
25 74
16 67
51 63
52 88
22 71
Output for test 5
45442
39382
19059
12773
27455
28851
34114
2066
21701
2337
11350
31754
39103
37471
18266
12663
13866
5194
21182
24269
22787
15283
9507
1257
18159
21032
23642
18746
14298
28108
3424
17949
2998
14133
17604
5108
16822
1214
12906
1839
32330
2686
2878
5830
34001
12551
11103
1894
12229
26044
1613
51267
15381
18483
936
16112
6799
22357
44556
39382
6568
31783
6109
8962
3844
2185
8250
25579
17902
4977
10347
20144
6841
13726
8315
7782
7782
12161
31793
1011
12146
13189
48269
4247
22387
12827
26267
27895
14298
16029
41232
17533
4160
8980
20680
28648
28842
7704
19862
28680
Input for test 6
200 200
93
995
36
543
407
912
933
730
109
559
146
894
210
689
200
73
953
717
733
790
934
726
727
578
877
404
740
340
246
42
870
615
407
428
543
382
180
70
457
876
990
847
160
5
555
320
683
299
478
283
55
36
109
859
213
327
531
962
746
103
663
966
900
132
788
53
893
683
267
470
751
43
818
549
895
473
447
260
913
559
10
489
231
412
967
46
959
971
499
848
231
213
64
568
842
496
291
119
753
756
967
666
585
849
863
192
763
679
658
328
155
959
4
808
255
689
135
453
620
950
978
40
231
260
397
789
409
677
675
184
706
710
435
543
944
920
564
368
321
469
983
289
395
318
739
702
518
987
297
993
741
691
610
664
568
218
794
113
834
390
715
89
2
327
977
881
994
986
167
509
245
96
631
555
992
685
964
189
184
415
534
769
140
108
343
489
734
52
39
359
637
892
418
426
896
397
636
163
371
840
56 94
151 189
32 135
93 134
72 122
1 155
62 154
24 50
8 98
57 173
65 196
24 83
23 42
80 166
15 184
4 90
12 75
21 151
80 110
139 169
22 164
60 103
53 55
46 115
51 174
131 181
122 177
21 69
17 31
7 86
22 133
120 127
92 108
30 162
71 77
116 197
72 162
97 189
184 194
108 150
60 101
4 144
77 141
44 156
143 186
47 80
40 126
93 189
73 133
65 121
98 152
98 117
34 52
38 50
104 176
105 108
53 61
109 189
105 148
7 24
87 99
43 50
76 103
94 187
65 174
190 191
16 51
57 151
114 164
98 153
42 163
44 104
85 189
172 187
3 163
96 98
109 148
42 111
34 114
76 107
94 165
54 76
158 188
35 170
26 100
75 103
32 103
74 171
116 155
51 74
19 102
123 136
54 168
67 123
27 198
49 148
156 179
48 150
3 62
11 23
18 119
66 119
29 63
50 141
7 97
149 168
157 176
9 59
154 196
68 194
75 87
87 144
7 44
191 194
67 111
32 74
8 129
117 154
28 80
168 173
14 78
57 106
101 180
61 156
79 153
44 145
138 163
96 175
79 141
56 199
4 124
29 88
23 64
99 118
101 127
187 191
16 120
119 154
39 124
102 110
107 112
7 70
134 144
12 83
5 52
79 165
64 69
144 184
44 52
7 193
97 194
59 143
33 99
39 99
152 194
34 86
23 102
94 105
47 184
133 150
44 189
35 84
33 93
99 161
29 78
53 164
66 135
80 125
47 63
57 61
32 172
48 53
20 185
169 191
28 49
94 149
150 157
138 146
66 176
17 20
11 93
122 170
80 113
80 183
51 194
1 138
26 182
170 182
64 184
22 98
4 177
105 194
36 128
10 46
146 156
177 195
71 157
139 185
138 188
6 189
Output for test 6
20700
19434
53363
22501
27318
82706
51750
12675
45585
64291
70505
28869
10619
47357
89953
45556
33133
69451
16874
17772
74532
23609
1181
36023
66445
28961
31301
24348
9677
40417
57426
4054
9666
69565
3976
43783
49568
49772
4497
23534
22358
74072
35125
59763
23558
17207
44998
51742
32748
31183
31479
11183
7647
6023
40675
2497
4513
42289
24062
10701
6854
2783
14635
51587
59843
996
18383
52790
27507
32089
63707
30919
56476
7828
84773
906
21565
35564
41261
17302
39977
13085
15109
72046
36449
15530
36025
53795
22962
11917
43447
7880
64042
30613
88722
53119
12537
54708
30266
7792
53159
28467
16206
48693
46399
11884
10982
24973
21417
67478
6661
31793
20180
2373
24491
20495
63128
21705
25540
2634
33209
27752
44645
53199
41698
52774
13808
44623
34418
77005
62976
29285
20004
11517
14682
1821
55135
21117
44269
5583
3542
32554
6114
36515
24208
47389
2816
22331
2714
98186
52504
46002
32436
30426
21425
25175
40264
7755
73168
10785
75705
23734
29367
36266
23728
60313
37395
23808
8213
3005
73837
1260
87620
9836
9793
31251
5279
4584
60732
3193
41871
27133
17992
56412
75814
72421
82397
6768
64955
37848
93746
47518
47173
19283
6989
8588
48178
25131
26774
96792
Input for test 7
300 300
196
646
612
539
871
448
320
930
365
165
947
539
190
958
110
715
344
108
848
330
671
445
495
604
790
738
190
665
132
262
996
430
600
658
132
690
701
675
586
865
567
832
828
903
849
92
668
444
20
598
650
53
300
284
522
206
61
259
645
802
159
526
679
669
982
62
896
86
530
14
173
527
316
524
143
49
147
885
202
943
265
743
388
524
38
825
873
268
388
362
519
428
683
524
353
199
438
18
72
885
307
460
622
948
629
569
662
685
313
141
684
622
795
192
14
620
178
638
143
70
613
572
300
131
278
594
388
988
699
573
36
732
981
568
545
986
77
876
776
305
266
255
437
704
522
293
239
434
168
614
801
516
960
536
268
299
583
274
612
461
455
868
67
886
695
413
929
442
604
460
60
106
330
653
457
135
944
167
944
410
59
36
994
961
232
212
758
315
858
216
805
628
763
431
334
969
198
933
690
556
94
721
898
899
592
34
189
803
920
365
681
362
171
730
94
12
743
497
50
245
574
727
427
816
361
684
852
682
160
291
912
336
226
953
730
522
289
169
51
677
898
436
240
853
645
620
104
862
710
84
344
576
809
544
818
682
98
882
356
565
914
273
198
801
292
35
636
291
172
508
879
334
306
755
69
409
430
380
613
840
23
533
504
47
951
479
69
788
481
56
367
623
915
124
688
693
229
118
631
492
53 134
50 226
155 166
134 270
113 176
55 296
133 224
17 184
71 151
129 164
57 132
124 236
89 128
155 223
82 188
56 137
262 279
290 291
17 275
152 249
250 294
52 225
6 276
64 267
150 178
88 287
91 160
24 46
25 52
94 189
166 188
6 145
135 279
273 277
148 188
43 240
4 40
7 84
32 289
46 118
103 155
62 263
166 249
86 153
202 267
76 287
98 185
132 221
243 288
16 17
267 297
193 250
65 169
4 152
82 207
182 197
35 185
64 245
172 203
139 284
148 218
98 300
249 300
114 279
97 198
31 213
56 285
58 216
247 300
137 234
17 112
106 192
119 176
230 269
159 224
92 196
211 247
156 220
90 172
38 238
65 233
67 280
83 285
90 211
179 266
87 276
58 59
156 162
79 91
69 286
173 174
137 160
232 296
67 114
9 140
53 266
152 264
46 106
160 261
108 196
287 290
19 165
137 139
66 118
24 238
103 203
104 185
119 276
179 184
162 220
83 175
26 91
139 293
73 104
111 216
96 262
139 291
140 252
139 162
69 127
53 100
48 141
22 193
109 253
203 297
144 289
58 262
82 195
83 288
140 192
26 212
105 264
38 51
59 244
106 173
132 180
297 300
154 285
125 226
40 204
153 226
42 269
181 272
14 15
43 113
87 231
32 248
27 207
212 295
108 194
64 77
142 189
225 276
68 299
51 287
142 161
55 147
112 237
53 247
244 260
96 180
246 252
159 254
32 66
64 76
53 247
45 95
19 291
98 282
149 166
139 166
58 109
117 291
78 110
100 167
59 210
183 256
45 265
19 289
122 192
152 237
207 224
94 201
58 143
225 285
1 280
156 202
34 223
106 140
152 185
56 68
32 140
177 242
99 178
40 287
2 18
130 288
134 256
128 149
26 160
6 142
164 165
162 245
76 124
18 111
247 279
193 214
32 182
28 251
270 271
132 139
246 251
155 240
55 68
94 203
132 236
144 237
235 244
195 210
131 157
9 194
251 291
208 231
71 90
40 217
54 299
189 261
262 291
74 232
263 287
132 248
66 206
108 293
4 41
37 198
84 260
146 150
87 255
22 278
29 142
112 168
12 254
87 240
225 262
134 157
40 71
82 268
9 272
182 207
150 207
73 146
8 94
201 254
44 248
16 284
235 251
114 171
35 82
57 214
142 147
79 243
87 132
132 260
25 282
33 165
189 285
170 171
248 282
113 220
289 297
94 158
1 17
117 272
81 269
12 131
43 129
96 212
173 263
20 193
112 232
24 199
32 275
89 172
24 173
116 160
64 141
1 131
84 181
109 214
218 285
196 203
42 146
99 290
99 159
258 267
137 183
14 56
113 152
76 224
39 268
Output for test 7
37129
84899
5881
69133
30470
117466
46973
81470
37745
18672
34268
58101
18025
34298
51672
37631
7381
423
127496
50389
20853
82967
133592
100280
14595
98068
33671
13785
15614
46491
10621
68024
72740
1969
20118
95553
20052
38209
126425
31988
26556
99721
42909
33354
33720
103950
42834
45735
22321
1059
14192
29865
50183
72499
62480
8710
72396
89077
16807
72203
36304
100111
24414
82048
50692
90475
111661
77101
25380
49350
46485
42685
28033
19894
33690
51748
17820
32302
40018
98350
81945
104553
100168
61202
45480
94072
904
3552
6338
106108
983
11276
31555
21857
64142
104087
58333
26444
53013
43951
1394
71914
1729
23369
105938
51471
40470
78983
3404
29618
44762
31608
76932
14339
52754
83989
75394
56431
11646
25414
20384
42725
83956
72363
46555
72932
101388
55707
101504
25646
92291
81039
8577
91243
32901
25113
1470
65864
52306
80890
37655
111123
46946
1068
32926
72121
106947
88422
40252
42648
5118
23426
25893
111976
114018
9431
42826
63147
94244
9552
41189
3300
49310
17997
4971
94244
22146
134014
91856
9476
13707
24206
86360
16159
34750
74792
39617
107426
133591
35746
44124
8406
53108
40279
30214
138719
24017
92548
17344
16816
6032
52535
34286
39180
120684
8807
79864
63112
11460
64760
66361
1581
43129
21927
45519
15729
12333
71897
110140
1387
5541
2724
43009
6554
54727
54414
47899
4865
9195
13777
90677
19107
12159
8583
86586
118728
38960
12519
78133
10554
60258
68053
91964
20619
78994
88587
1748
84617
126414
54446
28287
120144
76074
20208
12028
15224
93158
130355
14316
30324
34789
42797
27264
99383
131990
8234
27994
22752
77056
2450
81576
21206
66726
126879
64318
49239
520
17021
52983
4176
30968
8895
78260
93595
56819
39344
58695
47038
84957
60427
86571
119878
40406
72469
21909
36517
62858
47033
53102
33550
5059
49108
95213
30048
4952
22390
22554
18917
73188
112969
Input for test 8
400 400
157
36
342
166
395
797
194
120
125
500
959
74
129
274
609
852
659
416
239
848
756
424
756
153
454
815
659
462
719
2
580
309
305
325
522
439
837
962
349
267
939
520
422
927
783
356
770
544
298
5
518
341
136
863
818
419
230
545
838
73
573
593
869
136
272
493
212
976
366
316
605
479
176
917
777
671
711
248
390
413
753
490
421
872
318
889
829
562
543
872
90
747
172
428
106
397
60
853
613
831
245
824
144
878
951
467
994
754
688
882
832
341
964
448
357
936
767
572
425
403
899
949
896
459
525
40
802
79
594
502
537
147
267
202
427
388
227
819
762
479
130
487
193
995
774
880
767
213
897
156
782
23
950
225
227
240
174
225
466
24
486
490
609
858
565
425
262
675
625
479
867
476
644
27
572
770
708
489
878
908
988
806
879
202
573
716
739
440
215
917
528
764
962
503
318
771
262
72
812
534
76
582
183
608
655
541
376
117
681
85
747
677
769
943
740
853
467
535
987
43
129
432
753
68
820
41
281
774
283
76
333
496
784
969
328
689
922
768
458
574
976
565
416
559
655
347
642
389
884
491
892
631
771
582
900
132
975
742
446
352
525
850
54
459
136
346
622
535
93
609
377
248
302
258
511
663
45
448
447
796
611
833
321
747
101
773
78
135
829
744
414
81
820
46
116
922
417
513
701
705
31
132
298
598
327
515
506
830
901
450
192
884
892
417
906
453
822
424
741
215
772
623
225
783
328
830
118
528
222
574
94
876
617
944
514
730
102
723
361
577
828
237
4
433
636
684
651
645
902
454
423
111
95
653
3
185
23
670
264
104
707
347
146
408
57
103
656
8
462
385
392
496
652
599
719
452
589
299
347
273
869
211
905
577
554
18
213
438
459
419
58
316
403
800
140
875
665
720
610
178
47 364
1 143
60 235
176 242
295 396
286 328
11 171
49 241
312 350
153 349
66 186
96 351
47 291
173 236
295 391
220 234
45 283
83 289
370 386
109 195
316 343
181 192
112 347
105 237
166 340
27 359
124 343
312 356
70 78
60 134
36 80
309 341
179 264
116 359
96 196
50 252
145 231
313 369
34 64
291 300
158 354
267 321
47 306
158 265
201 376
154 390
39 192
147 179
236 309
28 59
245 263
103 400
293 310
61 136
43 375
48 245
227 261
302 309
91 351
23 319
76 231
106 187
167 309
1 307
15 247
1 183
49 209
239 353
34 249
34 134
2 173
146 254
222 303
73 397
252 390
185 378
176 247
9 248
62 138
184 243
5 385
261 330
134 196
111 292
192 323
138 328
237 285
135 322
13 142
87 240
20 122
100 162
231 340
294 319
49 349
33 372
103 295
29 365
157 362
80 105
146 223
238 391
39 150
29 60
120 376
118 305
36 302
234 271
143 171
220 310
26 330
111 346
45 189
98 219
148 396
119 387
64 320
85 330
69 291
183 369
24 367
36 289
374 382
388 398
116 253
201 334
271 335
245 284
166 193
16 87
176 374
72 133
100 250
14 150
274 400
254 290
38 104
16 258
201 236
51 216
302 350
116 177
153 215
70 159
124 167
156 252
150 203
190 368
91 395
27 54
15 95
220 298
86 235
22 185
78 160
242 346
185 351
222 224
32 272
180 377
37 243
301 323
186 202
84 318
118 303
44 348
107 263
280 398
269 399
279 293
212 284
146 156
192 241
40 57
230 251
109 357
46 166
198 316
244 399
26 282
2 198
336 394
26 38
261 353
203 257
300 398
102 347
62 379
210 243
9 165
118 129
199 278
87 380
61 271
8 123
275 360
75 335
191 232
5 42
1 192
117 216
91 301
163 195
12 186
247 343
127 375
109 139
31 38
321 335
88 392
227 342
14 369
71 195
185 214
143 180
203 338
13 286
44 157
27 151
268 385
204 239
136 163
17 152
337 338
253 398
201 324
8 113
147 296
266 312
231 301
67 382
213 319
45 359
295 372
168 339
52 307
205 298
126 206
89 131
69 315
101 121
167 398
217 239
108 361
204 245
200 221
1 251
130 156
41 74
12 37
91 345
280 324
134 217
186 271
76 283
164 321
150 207
25 303
17 233
41 367
40 345
73 346
387 390
231 380
244 258
41 48
243 336
6 176
146 285
106 346
125 242
344 370
38 216
135 367
92 214
105 209
69 347
242 381
32 109
85 136
51 182
162 243
66 298
305 313
70 141
78 366
179 213
49 326
50 68
95 129
33 55
136 252
238 396
202 351
90 130
128 387
25 271
111 231
2 145
1 147
119 355
74 345
213 225
10 363
155 284
225 230
203 275
101 170
78 238
163 238
104 194
21 202
185 199
293 341
87 326
171 208
126 176
13 109
29 82
143 236
53 379
183 307
39 290
119 125
39 219
137 399
72 149
71 305
197 248
153 156
122 180
165 259
30 239
90 196
79 230
106 315
19 26
193 266
18 107
100 118
195 261
17 254
303 346
206 281
179 248
58 186
270 397
191 195
236 262
51 384
55 136
117 179
64 152
85 165
105 199
112 300
96 348
116 322
5 77
87 397
137 351
102 164
75 141
29 55
19 136
158 330
17 111
107 115
25 168
209 278
1 292
364 371
113 185
124 337
316 320
192 265
64 112
272 295
124 334
72 157
100 240
144 270
64 348
184 360
90 137
172 375
141 308
211 221
201 244
184 285
101 248
189 385
94 289
51 375
93 328
4 313
347 398
286 359
152 338
160 309
Output for test 8
164860
73052
93858
37938
47806
22035
84579
103256
21769
103661
66273
136461
129851
34918
45272
6282
127169
110859
8337
47806
14265
7767
123624
72266
93102
173832
113263
23239
4900
40882
23392
18666
48665
125942
56588
109429
45492
26310
16217
4735
103581
27167
136073
59543
86890
118456
83280
16274
38127
16350
11260
152271
8828
41624
171877
105995
20607
4107
138004
157353
83448
45374
75740
158512
125419
95556
85456
58788
116675
54855
88374
59506
40888
166981
65602
96904
40557
127869
42097
31928
195697
33768
34266
95668
68373
100664
26006
98894
68994
83260
57047
33507
57974
13739
158953
175372
102408
174480
106058
14301
42042
74276
60364
15961
129935
96649
141136
21661
14552
45187
161208
123805
77647
68433
124069
135215
136273
130582
119329
93402
177782
135494
4358
5293
74606
69289
32584
20667
17534
38219
101473
35196
82912
73740
59680
17625
35053
132199
17921
89967
26518
31469
34125
48225
19779
53033
28147
89176
154589
14159
42348
39193
80738
87684
43597
53499
87319
1253
129057
100388
111913
12154
9211
125495
95724
161431
86424
56520
61131
7730
39175
5360
26617
9156
13213
129520
62926
60971
75048
137208
103381
24835
6936
45409
30792
46522
131038
164105
18781
81871
6643
41417
151015
114149
62899
41897
139373
20677
18744
100650
53442
111063
20387
93256
49204
125312
17136
4279
8048
155223
60453
184085
69296
16166
20024
70700
145719
60488
67267
55532
19228
13088
72810
825
68948
64158
56247
78068
21871
36930
163095
56212
164287
36621
91838
134444
48366
41559
24866
131529
13771
117419
11436
132019
22973
11328
132343
12696
17328
12617
134245
23640
45046
46149
111872
84756
30327
146586
115090
169623
161599
145781
1529
74076
9592
5261
48349
88804
73990
127590
61623
10215
97109
118469
66761
57242
148198
67648
41644
28895
71127
45928
123925
5497
39551
149480
19884
146953
8910
20975
12246
63407
76810
78117
23786
129817
132500
63342
74664
76468
122525
144921
7539
184053
68996
2275
38257
37174
87022
42449
51532
97651
8592
26143
127933
21478
23930
51450
27397
49946
168600
63835
134000
4556
98136
132577
43836
124354
26872
1642
29742
54009
111864
59003
81485
111572
4445
39594
47485
12875
36284
128598
23734
39821
38979
70172
59708
3075
17133
172294
44547
31900
48173
43018
52889
99076
134682
108895
36772
158935
113122
33898
37058
13856
63151
91287
51300
6260
75460
36933
151865
2471
38961
110533
2655
40012
27004
10367
109187
46613
76988
69051
150932
89629
25981
103911
87100
6890
23159
53255
80706
98172
104544
167772
124936
162126
21920
36270
97726
79197
Input for test 9
500 500
197
969
608
657
588
182
681
503
285
833
329
591
764
139
4
327
800
487
439
850
229
154
139
814
239
197
76
202
209
958
485
274
425
523
661
527
827
322
970
207
911
331
177
692
840
52
308
282
80
510
652
618
785
228
714
798
189
499
316
9
886
963
233
919
637
578
945
164
923
650
620
302
368
215
422
725
499
921
439
701
981
508
321
507
648
387
351
782
996
699
732
394
209
625
67
153
964
948
283
556
64
191
384
989
971
772
349
608
515
693
721
626
729
209
820
82
400
769
981
310
54
972
780
499
639
788
741
64
654
32
940
300
50
220
540
212
298
242
665
41
733
43
655
960
478
763
453
867
223
128
568
743
235
661
779
745
14
806
949
781
374
755
292
802
77
884
219
589
573
839
303
549
319
366
355
328
542
296
300
396
554
436
363
553
895
340
856
545
604
658
549
97
38
558
985
873
976
970
801
775
800
714
800
937
159
528
867
556
906
568
721
832
168
15
940
718
107
128
773
935
775
627
146
141
942
743
220
590
64
840
433
701
563
433
724
170
251
941
304
212
756
313
300
574
821
939
237
375
488
184
24
544
301
884
207
929
594
44
197
47
187
746
767
662
440
812
746
92
640
174
664
257
30
883
181
425
905
108
249
883
360
867
802
665
83
54
984
502
874
293
306
880
126
609
984
987
834
88
475
813
980
719
325
403
969
803
650
710
736
829
838
451
701
551
337
198
966
590
193
477
345
232
709
821
752
81
118
694
737
774
125
224
13
298
29
595
960
936
740
723
320
415
78
58
769
299
839
420
118
421
286
311
104
323
685
44
822
653
597
430
432
187
706
555
544
330
689
498
59
217
107
587
783
495
134
294
262
310
81
329
535
703
585
628
353
15
120
881
86
175
242
468
680
374
959
594
844
602
495
233
206
998
734
420
491
462
648
513
652
231
754
936
511
982
696
685
781
280
569
817
782
497
263
410
124
446
966
651
990
157
114
121
25
676
541
314
50
743
578
28
271
548
191
567
148
814
46
323
703
647
5
985
419
400
482
473
980
530
958
441
787
453
509
985
950
595
904
155
553
941
222
88
784
909
81
106
452
624
918
519
457
617
317
229
627
717
516
560
691
792
950
658
675
286
140
116
392
993
591
386
321 351
56 320
83 364
127 466
363 388
300 441
59 103
302 380
79 312
180 283
131 292
23 143
445 449
266 488
173 331
213 481
178 328
45 499
289 310
8 10
27 450
436 474
297 408
258 283
121 343
163 218
192 412
331 419
17 318
195 232
338 438
120 238
136 422
188 311
9 440
21 401
101 434
267 466
93 312
120 500
289 387
189 197
15 386
120 313
383 448
292 435
18 194
52 494
222 284
17 295
229 362
28 468
169 306
60 246
460 481
325 457
366 443
78 91
77 355
121 488
8 463
398 402
148 237
182 485
160 437
221 372
83 397
274 332
287 349
27 167
68 380
331 344
64 266
184 188
163 223
317 401
216 350
192 454
21 68
42 230
47 197
18 343
185 372
132 145
234 467
180 344
115 397
449 490
67 408
252 288
102 447
336 430
73 398
292 433
399 420
66 393
202 439
107 181
391 399
220 267
301 377
315 424
242 405
128 146
262 391
239 353
157 388
122 435
5 467
452 458
50 108
94 242
139 192
112 237
60 224
131 344
44 138
80 242
222 375
92 409
7 153
234 388
402 420
26 144
127 224
24 442
203 483
383 392
87 439
261 301
129 211
157 470
491 493
144 481
203 307
319 383
394 396
30 408
25 467
110 130
33 257
78 362
72 234
80 426
337 459
229 414
60 454
94 213
244 256
281 369
157 159
37 98
164 170
310 393
235 466
115 163
324 326
174 331
47 142
287 397
83 259
248 413
225 365
176 485
442 489
68 176
56 454
75 384
429 437
360 403
2 286
315 498
17 129
312 431
98 396
210 291
444 453
128 307
33 323
218 364
114 227
367 385
181 424
196 480
122 375
89 266
29 390
94 255
264 441
53 236
37 435
26 429
259 331
43 492
61 209
145 266
275 429
218 321
122 232
366 478
61 276
235 240
24 345
202 389
475 498
222 238
447 460
22 472
241 385
161 280
118 135
296 474
362 440
211 429
57 88
252 363
37 232
118 381
397 486
14 489
308 457
255 293
59 362
324 459
98 321
120 345
233 351
152 276
66 85
229 241
451 455
140 497
161 224
69 69
233 301
65 173
65 457
36 234
19 224
82 312
380 458
40 292
194 325
153 225
98 250
97 267
161 441
79 82
202 334
5 359
364 374
267 478
177 384
150 232
39 243
78 160
72 471
318 414
275 485
82 244
184 359
62 188
98 412
244 409
167 457
155 497
8 37
191 471
406 485
304 434
245 357
372 402
354 407
106 265
14 24
480 500
157 320
322 387
100 310
41 373
216 343
193 316
155 157
237 416
118 461
200 357
43 91
3 159
163 296
247 383
95 272
71 378
160 478
419 432
90 408
268 449
300 334
57 137
328 478
135 186
3 492
12 195
62 113
71 266
435 466
309 458
99 412
95 337
324 337
296 406
28 419
128 378
154 369
172 465
361 423
236 438
326 412
228 430
20 57
181 428
168 225
118 494
138 345
64 127
76 354
59 204
125 370
11 274
409 473
279 322
8 314
135 296
259 274
385 452
218 279
30 296
447 479
285 500
360 450
45 240
205 290
267 469
1 95
411 481
255 473
300 485
67 304
288 356
220 381
246 433
86 325
147 265
253 352
69 350
414 428
11 426
146 234
28 97
368 439
94 152
223 389
137 468
368 406
81 303
231 399
201 269
63 266
226 317
74 470
29 64
346 378
246 332
184 323
337 414
187 263
277 353
54 103
371 424
17 289
72 451
244 426
67 337
298 426
74 372
100 185
102 364
71 347
430 438
48 60
24 291
35 100
104 232
39 222
3 395
364 422
8 446
69 430
89 299
122 494
24 351
64 481
16 259
347 367
60 153
403 433
29 257
147 447
190 203
133 294
10 206
334 495
251 278
216 478
457 499
203 217
448 492
222 405
15 134
204 268
65 94
64 219
424 442
457 467
212 495
161 291
126 158
325 335
87 314
154 272
63 441
456 470
176 390
75 130
58 281
80 490
277 313
246 290
295 449
96 308
205 279
29 320
12 324
154 467
162 488
418 459
230 241
411 450
16 83
6 412
196 355
300 390
46 345
184 478
10 407
3 63
77 86
149 465
431 448
359 466
131 287
338 357
256 260
290 478
130 482
231 274
265 320
235 332
214 447
212 441
275 346
155 182
271 302
97 278
48 463
152 237
132 239
6 262
247 331
248 451
469 483
153 159
122 412
298 486
173 337
279 465
276 301
2 265
6 209
259 378
120 316
18 138
231 460
14 171
12 351
70 438
34 63
134 497
191 447
108 414
125 309
Output for test 9
13929
142727
147095
172901
10800
69421
24185
36943
125933
55452
83947
61612
2034
112478
85329
134059
81783
235497
14393
1621
216742
20479
54177
12168
117231
30919
112800
41355
160251
23774
47798
63685
147953
68578
220104
193620
171352
100370
117487
194909
48131
5338
189568
103510
32084
72420
90128
230541
30348
145298
66774
227677
73978
102007
12433
61806
36599
8973
146718
187929
232287
2534
49618
156109
141540
75250
161056
33258
34403
73779
161252
5514
108585
3189
34175
37501
68745
132664
22754
101643
79745
170840
97942
5437
116681
88212
143613
24081
176241
17915
176127
46769
167437
71203
13094
168246
119696
37839
5258
23873
37203
52148
79783
7890
63496
57481
118064
160656
237172
4269
32867
79739
27898
67360
90173
112066
50001
87955
75887
162087
74445
74973
12160
61380
52028
214553
141867
3553
181337
22417
44918
161421
2283
174184
55522
27990
1927
195627
228034
11563
120218
149384
88175
179464
58854
91864
202903
65234
6507
45910
1769
33699
3983
37099
115344
25098
1654
85010
49899
54920
93407
81306
71074
158525
25926
57182
204705
160461
2988
19539
147200
89871
59600
57299
152377
40124
4657
94462
155655
74055
61236
7649
126426
146385
130679
94072
185873
85617
88345
100125
206431
209334
39495
233173
82570
65141
79327
54622
60239
55618
114759
2602
169369
93216
12433
8529
7392
231100
70922
62185
9333
90300
37581
110342
17608
56833
106014
134604
47446
243499
71490
18665
159758
64115
119827
118368
60148
65753
11437
6392
2291
183939
35445
923
34773
58293
201828
107537
108882
123812
39275
132772
73410
41357
81848
90943
142379
2629
69736
183615
4864
106189
106521
46387
109832
44670
206294
44867
106387
87147
93154
67533
161596
81445
146926
176388
13290
144131
41706
64059
56896
14051
24684
84035
4382
11229
88747
28091
112949
173499
65821
68363
1538
89317
175201
81606
26771
80434
70432
66238
92990
159105
162918
6907
162866
89025
19162
43200
72882
25881
251920
93738
29947
103769
16464
71310
160648
128173
6221
54003
203115
127126
112830
150016
31079
99804
39255
101568
17455
128613
32984
194041
110275
36795
146758
79879
126322
136312
34227
25721
161935
85143
7344
33211
29382
141450
18408
109405
42701
105175
42834
101982
47979
37410
109649
92863
126701
35593
79408
92838
128700
63088
51306
149234
8949
213032
49689
37015
34542
30124
80442
170207
17039
118404
82189
35842
108818
48550
205402
18380
13541
45469
76972
37060
41735
40501
26613
27272
142100
193572
91209
144207
63759
155537
44013
137409
146702
2741
5680
139601
35726
70837
100045
199713
29491
223146
188312
111082
191927
171752
216668
127338
9496
49993
16708
122144
152645
9594
83442
103233
79984
12490
131042
24768
8822
26012
89584
61473
32888
17249
85458
7753
8092
142666
67975
15641
3845
122693
63256
195249
10214
108479
31224
118088
212407
22845
21329
76129
113732
36467
156295
164853
161957
167240
19632
6328
19745
34252
207673
84360
42817
158502
151626
202936
28578
5912
162355
6098
53250
81092
8711
1811
94761
179772
20590
31501
50835
114553
113239
38608
14222
17870
95302
214187
47832
57516
132629
44306
98855
7588
4189
148572
94143
87448
94670
15136
137320
107213
59194
104596
61634
113195
80901
176675
189973
15110
186116
129731
157582
98076
Input for test 10
500 500
489
849
603
712
711
719
391
120
916
221
62
817
313
669
680
548
161
479
134
743
924
260
404
50
404
487
230
245
362
823
796
887
249
53
521
846
31
986
689
224
56
450
368
840
356
567
674
621
751
316
514
880
278
488
139
331
881
977
567
581
115
529
649
711
206
944
62
846
382
947
494
859
653
372
379
714
822
42
609
372
824
40
114
21
652
927
881
423
305
507
441
750
132
757
532
96
4
74
854
610
191
925
556
179
855
937
631
259
544
170
892
271
241
769
986
807
670
124
764
408
608
546
655
867
653
799
458
394
296
184
684
334
864
225
939
254
883
230
352
158
66
567
243
344
381
637
118
53
591
928
883
316
612
300
915
282
878
670
730
949
119
975
313
239
579
250
417
493
806
88
586
24
590
44
971
581
563
201
766
809
117
805
588
660
89
975
232
28
362
15
708
128
773
918
634
177
738
720
614
424
276
807
653
172
283
266
156
470
943
756
591
454
3
917
359
551
452
368
769
678
351
209
63
628
528
417
288
190
923
750
790
869
811
111
111
382
371
356
549
995
437
418
835
266
801
385
873
829
498
366
625
508
568
40
199
871
251
288
342
227
185
773
275
990
455
614
984
289
70
249
308
557
554
570
701
919
7
124
147
462
439
806
74
90
356
372
462
546
979
103
144
779
540
711
545
57
581
995
380
906
245
574
895
281
484
114
455
41
7
118
282
985
289
102
584
658
213
551
576
748
431
228
231
538
741
910
777
886
73
690
517
763
578
651
687
753
926
990
492
84
761
442
350
559
715
924
276
178
635
307
646
406
577
14
679
956
804
299
648
870
849
226
599
682
748
57
984
68
366
94
8
644
845
577
596
502
731
381
10
508
7
539
454
174
575
1
675
853
170
825
262
287
872
288
228
969
76
548
755
210
976
303
652
245
237
382
621
775
38
824
509
5
106
695
558
717
126
428
532
680
32
793
393
490
341
394
391
868
548
900
542
562
145
166
844
138
42
50
462
42
495
185
94
160
829
137
285
659
18
101
783
162
960
637
504
231
27
406
627
416
180
867
400
253
61
529
146
318
36
702
255
62
973
335
850
225
720
731
242
374
993
880
581
29
632
454
913
356
256
513
713
815
716
875
71
426
275
726
64
407
384 395
137 235
7 479
147 154
200 407
116 252
86 396
182 489
115 451
165 382
138 295
142 382
94 402
4 138
233 415
331 403
143 426
153 333
459 487
188 226
55 321
114 139
191 311
239 476
44 109
128 393
237 382
188 432
197 418
8 424
78 261
170 408
136 303
40 55
50 129
12 341
109 177
54 432
57 462
59 429
34 345
273 406
274 310
41 481
57 59
43 282
265 363
339 441
5 441
233 489
50 156
159 371
5 409
54 399
76 175
301 404
188 482
128 278
440 493
153 316
7 212
43 248
424 489
242 477
235 491
115 463
223 347
110 298
301 475
152 497
195 421
9 78
385 396
63 487
351 352
4 93
48 434
315 351
82 319
434 479
8 56
137 382
298 472
233 415
341 398
463 500
391 427
180 222
121 288
327 438
413 493
1 253
147 254
35 452
323 484
88 121
22 166
359 363
97 483
69 145
107 411
292 348
137 165
3 264
41 281
372 480
191 274
244 480
319 432
143 429
221 224
8 43
174 344
205 480
327 419
84 452
259 405
20 284
36 261
429 495
50 424
186 375
1 173
56 357
209 322
75 459
20 462
285 498
33 60
447 464
206 254
96 373
107 359
56 336
175 359
157 466
244 360
65 434
56 467
317 368
242 317
79 462
389 397
208 430
251 451
336 426
105 118
266 287
14 371
156 289
392 429
103 390
109 277
396 421
89 233
256 315
17 152
182 218
154 333
50 389
98 131
107 271
15 131
329 416
307 474
27 354
38 280
413 458
151 331
158 202
37 103
28 56
179 215
62 365
318 412
254 462
53 215
230 254
51 441
53 355
247 439
253 442
291 358
18 484
212 260
173 195
193 396
354 493
291 466
205 366
90 300
85 211
20 213
97 359
157 495
112 434
54 370
244 294
110 117
46 141
32 72
18 282
134 455
90 116
96 307
135 152
44 464
243 314
37 209
109 498
100 285
162 366
94 224
62 151
340 412
280 300
175 408
91 485
142 259
239 291
62 68
183 442
12 115
31 194
146 226
59 453
143 144
7 453
225 492
341 356
96 481
106 358
145 310
71 245
77 320
81 266
16 327
319 358
329 399
133 456
159 447
232 437
137 363
5 29
275 431
469 473
12 275
49 260
56 414
67 362
156 322
228 356
145 197
155 309
46 467
232 365
223 466
279 420
30 82
39 417
95 413
71 254
41 159
109 234
36 58
20 427
21 335
218 300
266 324
68 473
162 475
195 245
54 97
178 183
48 115
164 234
299 398
138 319
39 353
191 469
96 378
3 232
295 454
231 244
91 448
199 307
161 398
68 381
354 380
102 277
47 190
48 387
133 408
209 216
48 60
33 440
183 389
198 212
278 345
168 216
415 432
139 215
4 440
345 473
262 484
474 498
56 65
3 384
12 425
176 375
113 455
145 457
431 441
278 449
8 54
231 487
355 442
68 248
85 444
14 272
130 260
10 156
479 488
96 123
22 126
403 455
36 81
290 322
32 404
356 460
185 433
145 495
227 324
404 490
95 394
78 341
86 182
102 210
46 59
100 229
425 450
297 363
11 391
128 164
90 152
214 237
29 442
465 498
137 376
56 90
218 273
30 158
180 185
121 275
38 447
196 385
286 330
19 361
33 294
185 409
261 394
9 212
65 207
20 72
163 359
388 447
449 487
99 496
19 194
84 104
167 289
178 372
409 461
96 344
101 107
115 251
18 295
129 461
22 433
60 327
212 441
14 426
345 396
3 36
199 289
9 478
128 384
366 374
35 331
30 129
81 185
325 388
99 348
233 364
358 387
7 273
2 330
30 168
60 90
26 413
138 317
170 347
216 482
25 338
181 215
141 305
259 307
245 479
143 291
258 395
36 383
56 129
319 402
130 499
402 452
48 379
384 422
220 362
96 155
437 477
148 374
113 229
119 362
171 364
279 484
309 416
468 487
77 429
167 365
128 459
51 114
149 368
192 270
117 328
93 121
100 315
142 228
52 280
304 469
135 275
191 478
303 399
48 205
25 498
13 201
60 162
283 405
277 348
285 358
56 426
459 496
244 376
198 354
401 482
286 328
80 139
27 156
32 68
143 291
303 372
212 479
26 119
436 446
393 425
202 236
118 245
77 287
35 73
49 130
114 126
16 140
45 436
369 446
154 363
274 451
413 441
336 415
158 433
172 278
31 393
45 46
315 358
69 137
121 345
316 451
195 289
29 199
30 435
430 497
254 360
303 439
283 303
58 470
149 213
33 152
43 400
92 495
210 282
79 174
396 482
Output for test 10
5210
48168
228086
3801
101618
69195
154626
145987
162800
107029
75744
119072
153128
69205
88774
37661
138579
88361
13784
18359
131245
14753
57671
111166
34489
130083
72211
119680
108471
205659
90539
116897
81514
7522
42058
164695
35130
188200
197894
183380
156096
65581
16009
213728
2425
120645
49743
47912
214410
120469
54401
105014
200592
172327
50022
51613
139417
73246
23868
78910
102982
105384
27994
109905
120773
168217
62032
93122
80672
165574
110526
35575
6005
205938
1052
45226
191871
21069
115059
17345
22963
120761
80795
88774
28324
17907
16738
20998
81586
55204
35811
128263
54409
203965
76586
17272
73333
3192
186445
38752
150841
29847
14311
131366
120345
47089
41950
109999
58222
140386
1251
16208
84241
129397
46885
178348
71517
131529
113634
29213
185642
94324
87598
151850
54119
185656
215737
101644
14234
7516
24874
138487
126166
140129
92261
147682
58229
182543
199614
29293
34615
185162
3977
109724
93752
44386
8156
9154
178531
65228
17892
143311
84354
11999
72947
26533
67963
18065
87749
169205
18861
81936
59825
44136
77229
163651
121805
18658
88219
22551
33888
14341
18386
153319
48677
97068
82143
13544
192256
150995
92530
89553
35314
226045
23870
11557
101187
63891
82633
80788
104242
64462
97474
131351
162448
158757
158967
23571
4806
49844
21865
131978
153962
13970
104171
7943
205302
32742
87386
188140
91995
101696
65246
45909
34940
10327
115565
189814
58532
24775
3947
124793
52707
83405
40101
192141
587
217353
127265
8425
185080
126455
79917
87777
118476
92623
153365
22798
36283
155057
138313
99715
112414
11050
76763
2028
132262
106741
178278
148251
79830
64506
26604
74980
204842
67578
114852
69320
28311
187890
156765
92469
61362
63463
12263
201665
156145
40232
26050
195407
148013
25680
22077
3286
35381
34564
49758
86117
157608
131670
141274
115830
75958
7301
173568
52427
115932
156596
13745
88696
72959
169554
135456
4574
7324
200359
101241
7585
33573
23884
9295
37198
214627
57227
104360
13701
5547
190084
204681
99503
166073
149959
3488
80449
22493
121516
40731
92039
175353
129307
63932
73382
5454
14626
54140
22282
24942
14602
185870
47088
121121
168464
45851
37203
148306
130361
49654
55735
7984
65275
9398
35730
189052
17906
31446
11886
203907
16783
118585
18738
27437
66737
3068
76782
200844
93432
21807
172162
129906
109542
65749
102471
71404
27593
96690
26080
17613
193136
88471
9817
59244
96341
21257
123383
4274
69673
137679
158211
203563
131775
110452
203945
25588
16540
43638
227333
125563
3643
147292
52846
52642
34317
125302
65961
13717
132701
162797
71801
15982
192310
84990
87444
126072
157176
16811
80402
22715
109359
71796
66834
174216
39443
43838
176282
20484
166621
18002
71364
30154
15224
113508
58255
121747
96731
95921
53991
10305
173370
99283
158009
32707
110921
39253
103216
14846
105551
42114
114393
75781
69215
136523
48408
80310
230792
94904
53351
60470
34958
38132
183762
18525
66074
77037
35400
21044
30720
66026
19183
71796
35700
125558
48486
2634
15404
17069
63634
103008
21329
42993
8656
63384
194450
33482
105052
83530
12480
39460
135054
52121
181416
923
24804
36411
111281
65279
45907
87473
202131
29366
52510
66128
10334
199458
33003
60574
178702
195055
35695
47473
37958