TEST DATA FOR `baabo'

Input for test 1

3
1
1
5
5
1
1

Output for test 1

17

Input for test 2

10
467
0
24
8
14
45
27
41
42
36
4
3
32
16
45
26
138
12
49
194

Output for test 2

55126

Input for test 3

25
15
42
33
47
42
17
37
9
10
1
38
25
41
28
29
48
23
46
39
1
26
10
25
38
38
7
8
17
24
7
30
40
65
25
43
42
270
0
11
15
7
20
669
40
39
35
321
39
153
45

Output for test 3

74918

Input for test 4

100
46
47
28
42
49
9
9
14
34
11
1
16
41
28
12
43
47
7
24
48
3
28
6
21
32
46
38
29
38
33
15
37
36
23
28
1
23
12
919
152
48
1
26
21
37
3
47
3
17
5
16
22
39
20
42
5
41
8
471
4
42
20
2
44
7
209
42
23
39
3
34
30
19
3
44
12
34
11
3
26
33
2
8
27
28
25
12
14
31
39
6
37
0
0
31
9
35
41
38
20
17
8
8
48
39
43
33
15
12
39
14
44
34
803
6
32
48
23
29
42
18
27
43
27
33
19
27
1
21
18
29
20
8
48
47
8
35
21
37
687
4
19
35
38
40
2
36
24
44
29
9
13
20
26
7
43
47
3
0
278
7
24
0
36
49
47
23
11
48
14
271
17
24
21
31
2
5
23
5
21
43
40
30
22
4
25
15
14
32
13
45
43
9
24
32
45
8
45
11
7

Output for test 4

1161530

Input for test 5

120
268
201
79
251
153
106
217
73
56
42
121
96
274
43
163
178
48
295
225
32
222
218
238
199
271
195
50
267
269
81
124
186
232
203
136
33
259
52
106
264
43
177
59
16
220
223
143
268
166
68
250
87
286
136
236
205
31
286
171
249
67
296
134
248
147
270
281
54
272
87
17
264
213
77
281
132
249
72
48
114
140
298
151
74
134
86
279
114
20
99
11
87
43
146
284
190
115
265
194
86
51
211
50
213
237
280
44
134
0
41
198
141
289
48
164
71
83
92
134
103
191
145
140
234
291
123
72
106
36
266
141
87
177
140
249
62
68
293
197
18
34
94
108
272
91
272
42
123
12
176
175
203
20
264
85
11
36
158
66
72
123
156
109
249
246
57
11
263
50
157
281
33
251
88
4
291
9
296
113
21
171
288
225
140
252
9
151
288
116
166
8
189
22
117
86
217
175
97
179
174
203
160
156
102
197
109
92
206
104
154
228
275
142
101
114
42
59
215
279
176
29
287
13
51
104
99
217
228
146
96
101
48
205
257
151
50
65
192
257
169

Output for test 5

3183587

Input for test 6

300
13
44
20
42
34
14
6
30
25
258
2
28
42
45
43
1
37
34
48
40
32
20
28
37
5
5
0
990
303
13
35
23
39
12
11
8
24
39
11
34
845
33
24
4
8
47
25
12
29
12
17
44
12
1
30
30
32
740
13
12
15
43
5
36
16
0
17
30
11
21
7
3
9
45
49
25
41
18
11
15
15
49
24
21
24
17
42
47
14
9
11
41
49
10
5
24
5
34
12
45
7
29
47
15
34
38
36
46
34
24
31
3
10
19
38
42
6
46
10
25
48
32
8
41
210
21
709
2
49
14
12
11
930
32
15
1
12
37
40
18
29
30
35
19
15
40
13
2
548
32
8
36
44
157
20
39
49
49
19
7
4
49
10
34
11
48
29
9
43
31
37
13
24
32
1
37
30
1
37
17
8
18
14
818
18
18
16
12
2
517
11
3
46
38
3
41
13
47
42
17
20
48
1
34
45
28
11
1
7
23
397
37
8
47
4
44
32
33
43
22
39
47
38
29
35
357
1
37
20
29
21
25
28
11
22
34
18
2
45
4
12
26
11
11
22
47
21
19
30
83
33
47
11
28
6
16
30
20
17
12
14
15
32
43
5
10
11
47
457
30
0
21
11
15
35
19
41
44
25
47
12
2
39
32
23
34
6
998
22
22
45
8
8
40
47
269
23
23
7
27
3
616
8
444
40
8
39
29
19
49
43
317
23
41
5
22
7
855
43
11
37
375
49
166
19
20
33
18
21
41
17
12
36
19
881
917
15
29
25
41
49
23
51
35
357
14
35
311
19
30
3
21
18
44
7
9
577
28
7
18
33
5
33
671
48
41
2
33
987
865
47
33
2
26
41
5
46
42
578
45
10
48
228
15
22
40
29
27
15
29
21
0
35
23
781
23
2
11
0
17
21
3
44
7
20
34
9
49
3
20
15
33
35
15
41
8
9
41
13
45
47
27
11
45
13
37
32
22
25
44
39
11
21
30
1
28
25
26
29
39
41
17
12
5
8
21
29
36
587
27
2
1
39
6
26
33
21
38
46
21
11
4
17
9
17
232
38
28
42
27
45
31
4
0
19
40
3
873
14
16
48
27
42
7
6
34
37
42
15
3
14
754
3
7
49
4
14
33
9
6
41
47
18
12
25
18
3
13
21
42
20
15
37
38
45
316
13
0
10
21
32
4
8
11
48
0
14
21
41
1
35
11
48
616
22
4
14
405
13
37
48
2
1
35
609
20
40
3
6
3
49
33
27
1
6
27
20
29
44
2
34
25
418
9
21
9
2
13
19
44
47
23
19
44
32
26
40
3
38
10
37
13
35
40
4
3
32
5
49
29
2
41
27
26
31
46
864
19
16
44

Output for test 6

7335082

Input for test 7

700
41
47
978
42
41
49
8
41
45
35
2
2
17
37
3
29
35
15
19
33
33
46
15
12
32
14
91
32
7
22
43
10
18
18
14
12
29
27
7
8
24
48
36
17
19
29
10
5
5
45
9
4
3
43
8
29
3
9
37
20
27
26
34
39
28
1
298
48
18
25
33
18
1
13
29
49
45
3
4
40
34
42
20
36
582
23
0
24
46
9
228
4
12
5
30
43
2
0
35
20
40
496
39
39
35
12
15
34
4
39
2
42
46
32
14
25
12
11
0
8
12
37
23
24
11
31
8
9
41
36
48
33
39
25
14
35
39
47
48
4
5
702
3
47
381
15
5
33
12
3
39
37
38
38
2
4
26
26
23
9
42
30
709
6
16
14
24
30
39
0
27
223
24
7
23
33
15
0
42
21
22
7
11
23
279
16
21
3
39
14
20
49
38
20
42
325
14
49
27
3
13
24
40
25
821
18
512
46
34
3
5
35
13
20
12
9
17
17
10
12
3
36
3
2
875
42
1
28
15
1
8
8
24
0
20
25
319
33
37
2
16
35
9
20
5
684
37
5
40
714
294
3
35
47
14
5
5
3
11
34
13
19
5
29
49
12
4
5
13
2
46
12
48
543
1
3
38
43
17
20
35
83
2
18
19
19
47
48
25
24
43
30
41
23
23
35
14
10
24
0
11
38
8
8
588
5
45
14
34
27
10
13
970
49
8
16
37
26
41
1
18
39
653
20
10
0
30
9
15
29
18
22
6
40
38
39
10
101
39
45
29
26
16
10
16
305
6
1
10
709
39
23
30
6
14
56
34
0
32
37
47
18
37
7
22
6
18
31
37
27
48
45
47
86
45
21
8
7
7
2
18
41
47
33
95
28
48
43
25
43
49
36
37
711
31
18
3
1
32
34
28
46
19
22
7
34
25
41
48
31
22
4
15
44
292
21
28
44
29
32
148
98
533
22
47
41
38
8
43
21
13
30
37
21
48
8
17
14
36
42
8
20
25
2
19
24
46
25
12
6
45
45
32
2
24
17
20
8
42
22
46
0
44
11
7
14
451
45
30
5
6
20
4
49
29
3
26
22
19
318
43
36
2
35
941
6
7
2
34
46
9
44
726
36
7
29
27
4
43
29
17
14
16
35
9
42
24
46
42
29
2
5
773
23
22
4
37
27
20
48
1
39
11
24
6
9
36
45
3
6
3
22
34
37
43
11
24
43
24
42
14
31
4
8
31
20
30
6
17
38
18
3
14
3
15
42
762
219
32
23
43
12
963
35
35
568
49
42
3
41
20
43
29
38
48
15
17
15
46
12
28
4
20
21
38
38
6
35
4
11
42
12
3
38
3
64
8
0
31
21
31
46
39
29
401
37
42
17
30
12
11
25
16
47
430
902
29
29
36
14
41
19
34
6
10
12
6
36
26
11
49
8
43
35
925
3
0
37
560
33
19
0
11
47
12
34
36
264
17
24
23
15
32
8
774
5
33
47
1
14
26
45
1
12
45
13
38
26
9
10
696
21
14
32
24
32
10
35
6
41
31
9
2
19
17
24
45
37
16
6
2
42
48
14
30
760
19
41
256
18
278
12
39
1
47
46
2
1
42
718
47
2
32
15
25
74
43
1
29
34
48
1
7
48
45
26
1
42
22
10
35
41
10
266
32
14
3
46
19
7
39
4
12
47
13
45
11
48
48
669
10
26
17
347
49
44
6
859
6
4
20
29
23
16
4
12
31
47
27
39
47
434
28
42
21
28
1
47
11
22
26
26
40
10
17
19
7
9
19
8
43
23
35
7
27
35
12
25
13
40
3
42
25
22
7
20
11
14
643
22
43
13
20
4
13
0
20
17
45
4
38
49
41
22
3
16
43
39
16
26
18
13
13
11
9
25
422
6
19
38
32
20
9
2
23
16
1
9
16
35
43
25
1
11
29
45
42
2
11
1
19
321
20
7
6
18
40
25
4
21
17
0
46
25
45
23
41
46
17
17
29
20
402
49
17
19
967
2
22
38
28
847
19
18
46
27
45
34
4
46
48
14
7
38
30
3
4
8
4
8
46
24
32
0
1
39
19
19
17
38
12
0
319
33
2
24
19
27
14
12
143
6
2
655
44
35
28
38
17
5
34
33
18
8
33
23
36
21
15
887
12
7
16
13
44
0
36
10
30
13
45
40
13
44
12
49
14
24
0
48
41
15
25
2
37
15
38
1
41
9
26
34
27
41
19
2
397
7
3
0
5
8
19
41
2
27
41
28
23
41
9
164
38
3
37
31
48
11
38
128
45
48
23
20
8
14
42
9
21
26
5
16
0
817
35
33
0
11
2
12
23
39
0
38
16
1
43
17
21
975
24
236
45
46
44
7
35
18
19
142
27
49
43
1
41
44
41
22
28
47
675
20
34
316
31
770
6
26
37
43
21
21
18
20
41
253
43
39
37
15
36
44
7
17
18
26
21
13
37
13
10
39
24
7
28
8
16
27
28
26
29
5
31
48
45
342
27
29
44
24
25
12
0
22
38
3
12
29
11
29
22
25
18
7
12
37
26
32
32
8
1
33
860
19
1
0
44
17
22
34
34
26
45
669
41
36
14
15
827
586
39
47
8
30
9
6
2
16
30
9
6
47
26
33
39
17
29
9
7
5
37
48
18
4
9
31
17
26
13
45
14
36
28
21
14
34
22
5
24
45
45
970
0
13
21
4
42
12
2
39
6
36
36
14
18
834
46
21
46
3
26
16
41
36
36
25
637
6
45
22
6
43
407
35
42
20
38
30
12
21
49
36
47
26
17
346
955
13
3
851
28
41
898
18
7
24
37
32
9
1
19
13
15
29
23
4
9
52
46
44
41
6
20
48
7
15
13
39
0
16
22
113
19
49
37
44
47
40
8
29
28
23
31
47
10
38
42
11
46
10
45
46
37
218
17
22
41
21
3
2
9
3
2
2
38
0
39
33
45
9
40
20
44
10
39
43
25
7
5
43
47
13
23
16
11
3
5
604
39
21
1
33
36
36
19
23
3
37
14
44
1
2
38
47
39
867
31
23
2
37
47
33
41
40
46
173
38
27
17
43
26
177
5
24
19
26
5
506
3
5
4
16
0
11
46
47
27
49
47
721
26
14
7
49
20
27
184
46
11
6
35
1
40
4
48
23
13
33
19
43

Output for test 7

16567426

Input for test 8

1000
581
381
198
845
5
161
175
107
129
9
350
785
37
440
515
307
114
733
633
904
966
91
409
546
845
522
806
138
465
598
467
736
669
665
270
674
516
446
471
335
145
821
119
182
261
324
180
375
56
813
970
713
594
378
949
438
590
444
267
746
732
734
481
401
89
752
765
605
888
236
941
32
56
750
905
7
765
84
383
821
587
42
223
181
420
862
309
700
305
576
445
37
310
617
128
89
368
893
384
255
819
14
978
566
765
882
573
529
967
646
39
243
688
954
114
798
815
424
498
120
1000
943
848
1000
249
976
88
617
558
473
562
377
487
539
943
942
111
205
160
768
852
200
10
229
153
125
27
658
549
525
468
238
157
315
238
407
981
16
714
539
179
967
606
357
505
238
298
306
443
459
73
985
349
84
214
192
209
241
850
448
456
8
686
303
13
614
710
995
631
114
223
810
80
829
166
275
757
155
582
199
614
655
184
653
429
398
845
328
329
384
776
785
82
152
87
96
766
488
90
86
602
3
897
372
522
753
647
278
908
919
477
211
264
351
864
693
439
398
712
768
473
177
242
555
329
330
651
786
508
431
872
800
124
458
171
646
211
508
924
118
117
91
330
381
442
884
764
882
973
475
339
445
343
582
690
672
912
341
147
109
462
19
909
587
477
770
232
688
277
847
497
84
938
517
465
69
400
920
951
372
84
290
507
427
872
197
790
473
228
937
272
380
646
180
657
123
950
580
501
917
426
688
1
363
204
156
122
605
75
73
667
160
53
865
277
615
61
66
778
980
3
49
359
649
229
16
462
869
596
654
785
712
341
786
765
546
633
887
841
708
960
507
558
703
371
526
317
122
592
785
101
285
834
151
935
753
167
86
621
453
740
96
164
81
882
929
627
204
505
467
603
465
664
160
858
726
686
866
848
969
650
640
253
484
791
878
236
648
965
858
100
394
954
955
475
525
573
792
420
77
949
22
232
303
873
781
28
559
646
876
217
295
515
470
779
996
38
706
643
693
253
433
86
897
77
252
111
340
43
531
108
683
553
340
986
426
811
704
675
456
269
892
752
475
51
220
470
780
926
804
472
869
236
559
765
4
811
877
344
544
407
452
917
961
483
592
76
293
295
751
750
565
332
191
730
73
101
199
854
718
2
325
586
930
574
351
934
384
918
968
619
324
420
535
975
593
127
741
886
422
491
325
677
513
206
406
587
308
296
130
25
989
455
611
918
29
652
541
103
569
509
722
584
619
948
558
211
74
299
787
186
480
112
554
994
318
960
270
626
946
400
341
935
545
643
542
574
294
83
368
864
282
780
137
591
727
695
802
801
684
588
988
855
390
541
538
709
190
808
24
136
898
366
761
442
699
302
707
993
385
74
546
357
854
683
948
581
68
439
71
752
27
749
296
417
980
834
816
861
331
531
997
228
587
757
671
285
749
377
277
825
141
514
181
995
196
820
265
264
258
27
707
976
776
2
83
756
527
899
306
858
429
302
86
706
749
757
991
497
824
268
11
965
782
193
959
668
703
915
623
961
942
329
937
407
21
19
853
548
608
158
96
728
150
182
433
589
629
424
777
452
382
788
416
854
671
64
521
373
979
143
334
610
162
961
708
875
980
250
112
277
409
208
4
249
390
438
839
18
862
615
160
934
402
576
787
73
641
998
136
309
141
470
610
994
430
7
868
99
257
671
377
666
879
381
916
960
509
754
668
60
58
829
994
150
404
780
914
735
778
50
735
609
210
344
292
331
351
160
430
608
521
497
965
399
569
570
358
77
13
26
138
71
545
131
221
639
602
135
374
379
876
108
678
85
142
970
416
183
820
847
481
340
33
445
740
602
14
788
370
718
504
198
789
48
329
701
688
621
836
752
1000
401
860
677
486
692
647
903
875
466
439
355
497
472
491
236
765
195
23
825
914
218
22
392
266
41
92
644
663
618
395
352
18
254
720
505
636
366
407
510
522
536
556
709
698
737
945
152
932
659
977
535
877
689
928
833
731
19
477
393
638
872
435
346
817
154
851
142
210
948
653
423
483
899
131
872
635
76
23
256
425
0
792
992
689
409
514
109
428
681
192
756
243
628
102
59
782
643
892
683
591
544
105
764
132
236
635
457
2
349
714
117
39
195
108
418
604
313
528
722
994
720
478
236
37
270
986
510
913
878
192
503
111
297
958
244
223
282
701
226
631
104
343
670
299
142
779
593
455
306
315
448
716
483
375
444
753
360
954
665
237
145
859
349
132
816
283
355
788
674
581
419
779
615
779
768
447
557
361
902
553
366
39
269
849
414
403
601
775
356
956
702
191
814
50
323
319
333
678
107
698
950
216
476
254
685
934
701
242
985
292
485
350
21
444
198
126
847
489
901
202
445
292
393
949
343
406
268
366
775
65
63
414
972
229
668
656
163
58
898
147
40
73
188
61
517
386
187
364
566
778
256
10
70
650
649
103
746
917
159
520
672
914
934
643
142
291
299
996
349
887
834
389
960
21
141
167
97
328
531
663
797
787
363
867
126
12
660
873
619
819
392
982
422
16
624
255
307
613
250
657
500
774
736
149
795
877
316
893
896
537
245
692
14
609
248
140
311
908
703
930
416
786
601
839
802
225
784
108
528
33
455
718
808
882
868
292
448
874
875
343
101
120
725
115
729
663
946
730
260
649
349
677
434
951
205
235
175
989
33
393
712
179
111
209
60
979
192
508
542
66
542
333
186
266
448
605
930
394
334
189
733
684
556
166
324
451
91
189
129
124
582
532
303
693
431
53
361
623
562
904
690
103
927
566
59
375
171
679
459
195
559
191
569
805
47
893
256
138
81
75
953
664
607
947
356
729
1000
718
351
251
311
731
354
237
297
104
302
468
783
451
353
341
332
923
837
379
815
92
207
897
858
160
250
155
797
606
884
796
13
925
47
14
656
91
252
953
195
244
110
669
386
463
700
718
75
536
97
891
318
995
477
176
845
727
21
641
22
905
127
36
829
174
50
174
956
993
126
842
928
927
200
313
80
900
30
155
126
818
736
444
503
212
310
347
629
331
989
652
926
806
378
445
980
118
619
625
111
436
466
729
362
666
41
132
256
762
979
382
270
714
516
773
617
517
810
936
538
798
587
464
293
965
909
272
774
527
588
885
963
53
303
15
410
344
147
666
796
125
738
65
530
253
528
146
770
338
772
308
826
359
462
119
13
370
81
787
587
669
361
240
413
664
255
823
698
402
178
184
218
916
940
438
168
468
584
629
496
355
627
321
404
779
440
108
839
212
895
425
881
947
665
984
300
610
806
999
703
984
873
921
589
812
358
448
970
632
76
465
677
393
787
772
171
917
880
700
128
464
124
700
100
480
373
401
89
179
89
792
853
962
402
442
773
450
890
743
81
656
898
449
739
684
911
600
291
790
299
109
944
113
499
44
593
873
445
373
51
224
164
594
185
567
726
648
707
305
80
479
651
979
928
79
352
528
679
643
317
668
753
951
782
251
685
64
123
820
437
865
43
292
149
919
549
875
567
255
871
337
734
521
315
351
601
358
879
970
0
886
638
443
837
109
695
211
864
508
31
301
63
74
593
212
994
832
777
250
86
647
277
511
168
593
862
459
641
741
428
641
316
65
84
843
865
469
54
729
667
85
720
730
850
2
632
533
834
409
473
610
746
751
120
604
33
983
62
674
413
491
4
419
246
779
262
111
938
316
530
605
91
249
24
631
942
347
855
775
446
327
384
191
768
195
796
801
177
858
164
280
38
169
699
285
638
651
86
576
967
306
871
748
245
895
69
186
241
924
651
377
941
725
569
709
920
54
199
787
602
54
757
641
914
456
616
551
106
392
126
764
698
997
201
943
582
961
819
513
884
469
891
515
884
149
223
494
203
112
280
805
166
728
445
79
874
751
321
980
142
447
433
840
134
325
472
406
285
981
609
860
139
189
374
23
338
287
517
231
399
487
36
256
214
171
25
87
923
346
758
64
484
881
595
308
896
757
714
181
738
12
731
877
202
104
900
230
391
106
462
480
284
498
736
498
669
452
276
281
798
33
36
281
604
631
589
500
387
993
371
815
696
101
692
898
205
281
127
286
78
589
456
362
777
883
860
136
334
826
417
131
549
143
103
153
774
382
343
852
65
714
356
761
815
47
348
710
19
475
686
97
755
141
459
531
23
8
357
47
835
465
179
383
608
973
226
72
354
569
614
419
973
970
870
477
708
217
186
727
383
562
824
137
394
973
358
107
981
716
155
505
871
334
579
478
997
805
550
350
64
854
460
36
824
329
514
531
237
390
948
620
643
771
447
36
433
805
143
413
210
298
609
80
322
187
249
318
682
489
359
436
343
509
163
166
838
677
387
765
757
334
384
399
104
831
435
537
326
269
640
536
567
939
307
580
816
556
898
498
44
947
624
387
455
787
243
984
153
630
748
911
964
132
1000
758
653
125
985
979
394
315
205
651
253
202
230
69
448
819
257
182
765
571
260
220
358
503
203
511
824
951
111
477
773
802
926
116
927
600
785
10
915
680
661
859
882
582
618
19
90
565

Output for test 8

298017778

Input for test 9

1000
272
9
6
7
7
1
6
1
3
0
3
2
6
1
7
7
2
6
2
0
9
2
0
3
7
5
6
9
1
4
8
9
1
5
5
3
5
8
2
4
5
3
6
4
7
4
4
9
6
1
3
2
8
0
6
1
7
4
4
0
4
8
5
0
8
5
2
1
2
0
6
4
5
0
5
4
4
6
1
4
0
3
8
1
4
5
5
6
9
1
3
8
3
9
0
8
3
3
6
9
9
9
1
4
0
3
4
2
9
5
8
0
9
0
1
8
4
6
6
2
7
4
2
1
3
4
7
2
7
3
8
8
9
5
6
3
6
2
9
5
7
5
6
2
9
5
6
4
2
5
4
1
1
8
7
7
5
1
1
1
9
8
0
3
8
4
0
5
5
3
3
9
6
6
7
6
9
5
5
1
3
2
1
4
9
1
0
4
9
2
4
8
7
8
4
2
5
2
3
6
6
4
1
7
9
6
6
0
4
0
0
1
8
8
7
7
5
1
3
9
6
5
1
5
9
6
7
8
1
2
2
4
0
3
3
1
8
6
0
2
1
9
1
3
8
4
7
6
5
4
3
0
4
9
7
4
9
6
2
8
7
1
2
3
4
1
0
7
2
5
5
9
7
8
7
0
4
0
3
2
8
9
3
8
6
6
3
6
0
9
2
9
6
1
6
5
0
5
4
5
6
1
4
7
5
5
7
9
7
8
2
3
1
8
3
3
0
5
4
3
3
9
0
8
9
6
2
9
7
6
3
6
4
4
6
0
1
0
6
4
2
8
0
8
4
7
2
4
2
4
6
6
3
6
8
9
3
5
9
5
0
9
1
8
1
7
5
4
1
1
0
7
6
1
8
7
3
6
1
1
9
9
1
9
3
0
7
8
9
3
8
7
6
7
8
4
2
2
2
6
6
5
362
9
0
1
9
7
0
9
8
5
6
1
7
6
7
7
7
5
8
9
1
0
2
3
7
9
9
1
4
5
2
1
0
4
9
0
6
1
8
4
3
8
8
0
8
3
0
9
5
9
1
1
4
3
9
4
7
7
4
5
6
9
8
2
4
8
7
3
2
0
4
7
7
6
3
5
2
2
7
9
7
7
3
8
3
9
4
6
7
1
4
4
3
3
4
7
6
4
9
828
0
3
3
7
8
9
2
8
8
6
1
1
0
4
6
1
5
9
2
3
0
2
6
8
8
1
6
3
9
6
5
0
0
4
2
9
4
0
8
4
8
0
9
4
3
0
1
5
5
3
6
9
2
7
7
2
4
5
3
5
6
2
0
9
3
8
4
1
2
1
0
1
4
8
3
8
0
4
6
0
9
3
5
0
7
8
7
6
4
6
5
6
7
3
7
1
5
7
5
5
0
8
8
4
9
6
1
2
8
8
3
6
8
1
4
9
5
2
1
2
4
6
8
4
3
3
9
2
6
0
4
6
5
4
0
0
1
0
6
2
8
3
9
2
7
4
3
5
9
8
3
6
6
8
2
6
3
5
5
5
5
3
2
4
0
0
5
4
0
9
9
5
3
2
3
9
8
7
4
0
6
0
5
8
9
0
2
4
0
7
2
6
2
6
9
4
0
9
3
9
7
5
9
1
7
1
9
3
0
7
8
2
3
8
5
2
6
5
6
2
1
3
3
7
7
9
8
6
4
7
9
8
4
5
5
3
0
8
3
3
1
5
1
1
4
9
3
7
1
4
3
7
4
7
5
9
2
5
3
0
9
5
8
2
1
2
2
0
9
5
2
8
7
1
9
9
0
1
4
1
9
1
5
4
8
4
9
0
6
7
5
9
0
6
2
5
4
4
4
4
2
2
1
3
0
1
7
4
9
3
3
9
8
6
8
3
2
2
3
0
1
5
7
5
2
7
4
8
1
1
9
7
7
3
1
9
2
4
8
3
8
9
2
5
8
0
8
6
0
2
0
9
4
4
1
7
9
0
7
5
2
1
7
0
4
7
5
3
6
4
1
2
1
6
9
6
9
4
6
3
1
6
5
9
2
7
5
1
7
8
3
9
4
3
7
7
5
1
8
6
5
4
4
9
6
1
7
1
2
5
9
7
9
6
6
8
7
3
2
5
4
4
3
0
3
1
3
3
4
5
5
3
5
5
4
3
9
7
0
4
4
5
9
1
1
6
0
6
6
6
0
4
2
0
2
9
1
3
1
8
0
0
7
6
8
7
4
4
7
3
7
2
6
5
2
7
2
7
2
5
6
5
2
7
9
6
3
7
5
4
7
5
5
4
6
9
1
2
7
8
7
9
2
9
1
5
5
7
2
3
9
9
8
3
1
5
5
6
8
2
4
5
6
7
2
4
7
7
4
9
9
2
6
1
2
6
1
6
6
6
9
7
7
5
3
3
6
1
7
1
4
6
8
1
1
6
8
9
0
5
4
2
8
0
6
6
6
7
4
8
5
8
6
3
7
4
0
7
2
0
8
4
1
0
7
0
0
4
9
5
9
5
7
0
3
7
4
6
2
0
5
2
3
5
6
1
3
0
8
4
3
0
2
4
4
3
5
5
9
2
4
0
5
2
2
1
5
0
3
3
0
3
1
5
7
1
6
3
1
1
9
2
1
1
4
2
6
8
7
8
9
6
1
8
9
2
2
2
6
7
4
7
1
1
6
8
6
3
5
0
5
6
8
5
5
3
7
2
7
2
9
8
3
4
4
0
3
6
5
7
6
3
0
4
0
8
0
5
3
1
4
7
7
6
7
7
4
8
1
5
1
6
3
5
4
8
3
0
0
0
9
2
6
1
9
0
2
3
2
6
5
9
0
4
5
9
3
4
9
6
0
6
4
2
7
9
2
9
0
1
2
1
5
2
7
8
0
5
7
4
6
2
4
2
4
0
4
5
5
8
9
9
7
4
7
4
3
5
6
4
4
1
4
6
1
4
9
8
7
8
7
5
7
4
8
3
2
0
7
7
6
6
3
3
8
1
1
3
5
6
8
9
2
5
7
8
0
8
3
0
2
0
3
5
5
6
8
6
1
1
7
5
5
2
0
6
6
7
1
1
8
9
5
5
4
7
7
2
0
4
0
0
3
5
5
6
5
1
0
7
7
1
2
9
5
1
6
9
2
6
2
1
9
2
6
4
7
9
2
7
8
9
9
7
9
8
0
3
5
9
7
8
9
4
7
8
8
9
509
7
6
0
0
2
5
4
9
6
6
4
2
5
8
0
9
6
4
2
9
2
1
4
9
8
4
7
3
9
1
3
6
8
3
9
9
5
2
8
6
3
0
2
5
3
4
8
6
8
1
4
5
6
0
9
4
4
4
8
4
1
9
8
4
0
3
8
3
5
6
3
5
0
7
5
8
7
7
4
5
6
8
4
2
0
7
3
6
0
0
9
5
8
9
4
1
2
1
6
249
3
7
4
3
0
3
4
0
9
0
3
5
1
4
3
1
2
8
0
0
5
8
0
8
2
8
5
6
4
1
6
2
3
0
8
7
8
1
3
4
4
5
9
4
4
6
0
2
4
4
3
4
7
0
3
5
2
1
8
7
9
2
7
3
5
9
6
6
5
5
1
8
4
1
8
5
9
2
4
9
0
4
6
2
2
3
5
7
4
7
6
6
8
5
2
2
0
3
5
8
1
3
5
5
9
4
0
1
2
1
2
5
9
4
1
7
5
9
6
9
4
1
1
6
1
0
4
1
0
4
0
9
7
4
9
0
6
4
8
7
3
6
0
7
7
4
2
9
5
9
3
0
5
0
3
9
3
8
7
5
6
5
7
0
6
3
3
3
1
3
3
1
6
9
8
2
4
0
2
3
6
7
3
0
2
2
7
1
8
8
5
2
7
0
6
8
1
8
2
7
1
4
7
8
9
3
7
4
9
1
5
9
4
7
2
8
4
6
9
0
2
9
5
9
3
3
5
4
1
8
3
9
4
155
7
6
0
6
7
0
6
3
8
7
5
2
6
9
2
4
6
9
1
9
6
6
8
5
9
4
5
6
5
8
0
4
5
7
8
3
3
8
5
4
3
2
9
6
1
3
5
5
0
8
4
8
4
8
3
2
4
9
5
1
4
3
7
4
5
0
2
2
9
3
4
1
7
4
3
8
9
2
5
5
3
1
8
4
2
3
0
3
6
1
0
8
8
4
1
3
8
5
4
9
1
4
0
8
5
7
8
0
2
6
5
5
4
7
6
3
4
1
0
7
4
1
7
0
6
8
4
6
5
2
9
9
8
9
6
1
1
2
9
0
3
9
6
0
8
0
0
0
8
7
8
9
9
9
6
4
0
7
9
9
6
9
4
3
2
7
4
8
7
9
8
7
4
9
2
1
9
5
5
2
5
3
9
5
6
8
8
8
2
1
5
4
0
3
9
7
7
3
3
9
8
0
6
4
0
5
5
5
3
7
6
9
5
9
1
8
0
4
9
8
7
9
5
6
2
7
1
7
7
7
4
2
5
7
6
5
9
3
8
3
1
2
2
7
1
0
3
4
5
0
6
3
3
6
9
8
2
9
6
3
7
0
2
3
9

Output for test 9

455453

Input for test 10

1000
272
8
362
1
828
3
791
5
617
8
776
1
863
2
175
0
975
8
959
1
282
0
710
5
796
7
206
7
783
4
454
0
363
8
227
4
590
1
238
8
454
3
469
0
362
2
258
6
967
9
839
2
280
3
498
4
229
3
161
5
276
0
474
6
411
7
641
0
518
1
522
7
774
7
406
4
919
3
252
6
923
2
677
5
724
1
748
9
297
1
376
0
283
9
568
1
201
1
203
5
312
3
215
9
514
9
196
6
349
4
226
1
394
5
161
1
967
2
129
7
347
4
689
8
778
5
826
2
338
2
595
8
725
2
434
3
520
5
846
4
934
7
740
7
315
3
593
9
236
3
140
4
297
7
885
5
746
3
707
6
207
9
822
3
366
0
927
7
859
3
527
4
220
7
560
8
390
4
768
6
467
5
800
5
442
6
221
1
936
9
358
0
203
0
896
7
620
4
828
4
400
0
979
7
373
0
801
9
628
0
681
0
606
6
724
8
709
4
100
1
287
5
121
9
808
0
201
5
942
6
132
5
892
6
479
9
939
8
909
0
668
5
125
0
726
2
626
5
640
5
465
9
645
2
203
9
692
4
344
6
599
3
406
3
241
0
546
1
257
7
232
3
885
7
121
4
857
4
837
5
114
4
571
4
875
5
707
1
309
2
835
6
903
6
616
7
726
0
431
9
963
5
753
1
383
9
139
0
632
9
460
6
800
0
853
2
805
8
311
2
890
2
234
2
502
8
570
6
504
7
798
9
870
6
189
0
978
1
865
6
602
8
414
8
948
6
233
9
568
2
831
3
247
5
823
8
245
7
225
8
228
8
240
0
674
7
296
9
780
8
187
3
949
5
913
1
426
1
474
0
686
8
433
3
192
2
552
8
266
3
814
9
844
4
260
9
684
7
192
9
4
7
3
1
3
0
5
9
7
4
9
3
8
1
3
7
4
1
7
6
7
7
4
5
8
4
1
7
4
7
5
0
6
8
7
9
2
0
4
3
6
1
5
6
0
2
6
5
9
7
5
8
9
7
0
0
7
8
5
9
1
5
7
0
9
9
1
1
9
1
8
2
6
9
5
8
6
0
5
0
4
8
1
0
5
5
4
3
4
1
9
6
7
3
9
5
2
8
3
0
8
2
5
2
4
2
4
6
9
9
7
3
9
2
5
4
6
4
1
1
5
2
3
3
6
1
7
4
9
6
8
3
4
0
9
6
9
8
4
4
8
1
8
5
5
3
4
5
4
7
9
6
4
2
7
3
5
0
8
9
9
1
8
3
2
5
0
6
5
6
0
2
4
1
4
5
4
6
3
1
8
0
9
6
3
4
6
8
7
3
3
5
6
4
3
0
2
7
3
9
4
8
8
0
8
8
7
5
0
8
6
4
2
2
5
9
6
1
8
2
5
5
7
5
9
5
4
6
9
1
8
6
4
4
2
3
7
7
1
9
8
6
2
8
5
6
1
2
9
8
9
0
8
1
3
2
2
6
6
3
2
8
4
5
8
0
0
9
8
5
2
8
9
1
1
2
3
3
3
0
5
1
8
0
8
2
0
2
6
8
3
5
9
8
8
8
4
1
3
3
9
1
8
2
8
7
7
1
2
0
6
3
2
6
8
1
0
4
2
7
2
1
6
2
8
5
4
0
0
8
0
2
6
9
6
3
0
1
2
1
5
6
2
2
3
8
5
7
1
8
3
1
4
4
1
4
4
1
4
7
9
8
9
0
4
9
6
0
6
3
9
5
6
3
6
4
5
7
3
1
5
2
0
0
1
9
1
8
6
8
7
4
0
0
1
2
2
2
0
8
6
3
7
8
0
2
4
3
0
6
4
9
4
6
9
6
1
5
8
5
7
4
7
7
1
8
8
5
8
8
3
9
2
2
8
0
2
2
1
9
1
3
8
2
8
1
9
5
1
8
8
4
0
8
0
3
3
5
5
4
3
4
3
9
1
9
3
4
2
1
4
6
1
7
4
0
6
8
6
3
2
7
6
4
5
7
5
0
9
4
1
4
5
3
9
1
9
7
9
0
5
6
3
1
1
9
0
9
9
0
2
3
7
7
5
3
3
5
0
0
7
4
4
8
7
4
2
5
7
3
0
9
6
9
3
7
5
1
3
2
2
1
8
7
0
3
1
5
4
9
9
4
8
7
9
7
3
1
1
6
9
4
8
9
1
8
7
0
0
7
0
4
1
2
9
2
2
9
5
1
1
4
9
6
0
5
6
9
7
4
1
8
7
6
5
5
1
6
8
9
2
4
5
2
8
8
3
6
6
0
9
6
8
1
7
5
6
4
8
6
2
2
9
6
0
5
0
5
4
9
2
5
7
6
8
7
5
6
0
8
8
7
6
5
4
6
9
1
0
4
7
6
0
0
7
5
4
7
1
0
6
8
9
8
9
8
9
5
2
5
2
4
0
5
6
5
5
7
5
0
6
0
0
9
6
9
9
6
3
3
6
7
1
6
8
4
6
0
1
2
6
8
5
9
0
3
9
4
3
4
5
4
7
2
1
9
8
5
9
5
6
0
3
0
3
2
5
2
6
9
4
7
8
1
1
9
3
0
4
8
3
8
0
7
4
4
2
1
4
9
0
0
5
8
5
3
1
1
8
9
0
0
3
9
1
4
8
8
2
7
7
0
9
9
9
6
3
8
3
5
3
3
8
2
3
7
7
2
2
6
3
4
4
5
4
7
8
9
9
3
3
3
7
4
1
4
5
3
8
4
9
2
2
6
7
4
4
9
7
4
5
3
3
9
8
5
0
9
7
0
1
8
1
5
0
0
2
5
5
9
4
1
7
9
8
0
7
2
1
4
7
4
6
5
3
6
3
2
3
4
7
9
5
0
2
1
1
3
2
1
8
2
6
9
9
1
6
0
8
9
2
5
9
8
9
1
3
5
1
9
5
8
3
1
3
3
2
3
1
9
2
5
1
2
5
1
2
8
4
3
2
1
5
6
2
2
2
6
3
6
2
9
4
0
1
2
2
0
6
5
0
9
4
5
0
6
2
9
9
1
4
9
6
1
4
8
5
3
1
0
7
8
5
2
1
4
5
1
8
2
3
3
4
0
1
3
0
9
2
9
7
1
9
7
2
2
5
1
4
3
1
2
9
5
6
4
5
2
9
9
4
3
5
5
0
1
5
1
0
2
0
5
1
5
0
1
0
0
6
0
4
2
3
1
0
8
4
6
3
7
4
8
0
0
3
2
6
1
5
7
6
0
4
2
4
3
4
3
2
6
3
9
9
5
0
8
6
6
0
2
2
7
0
7
1
7
7
2
7
2
7
1
2
8
0
1
7
8
4
7
1
6
4
3
7
9
4
0
4
1
0
9
4
2
9
1
0
9
6
1
9
7
4
3
3
4
0
7
7
4
1
7
3
9
8
0
4
4
9
8
1
0
1
7
7
9
7
2
3
3
2
2
3
1
1
2
2
1
8
2
1
8
0
6
3
5
4
2
5
6
4
6
1
3
7
3
5
5
1
3
4
7
1
6
9
2
6
1
6
5
2
0
1
3
0
8
1
1
3
0
8
9
2
5
2
8
1
2
2
6
7
2
4
5
6
5
7
9
7
1
2
3
6
9
5
0
7
8
5
7
509
7
249
3
155
3
301
7
710
3
247
8
632
2
738
2
379
2
272
0
840
7
762
5
513
7
613
3
650
2
598
5
902
3
554
5
206
2
629
7
791
2
481
6
406
7
245
4
627
8
266
9
698
5
270
9
601
7
483
3
879
9
605
7
728
4
554
7
601
4
254
2
504
6
339
6
474
6
888
2
351
5
561
7
512
1
831
9
908
9
728
7
403
8
702
4
761
5
574
9
582
9
467
8
186
3
338
4
718
2
162
6
588
3
535
7
710
9
388
1
523
9
326
5
215
0
843
3
146
2
150
4
643
0
415
8
455
2
971
1
558
7
207
7
293
4
958
9
713
4
820
9
235
1
438
1
529
0
942
6
794
8
141
0
870
7
356
5
692
1
532
2
998
2
599
9
770
0
655
9
282
7
501
1
207
2
152
8
371
4
316
2
849
9
224
7
300
5
880
1
208
8
721
0
699
6
693
2
223
3
437
6
259
9
832
4
720
4
706
8
982
2
504
1
970
0
386
3
355
4
195
7
920
8
140
1
558
5
269
8
443
1
691
3
647
6
518
7
768
0
633
9
546
5
338
5
502
3
206
1
577
1
844
0
761
4
798
2
102
8
258
4
635
6
590
6
270
8
388
0
752
2
824
6
394
4
541
4
324
5
185
7
936
5
617
5
954
2
862
1
335
1
146
8
250
6
345
5
731
1
720
6
851
0
204
5
613
8
122
2
528
1
506
4
101
4
852
7
433
8
748
0
273
1
555
7
787
4
689
5
510
6
994
3
123
6
288
9
785
1
497
2
977
2
532
1
102
2
113
5
211
6
984
5
780
1
657
5
364
7
240
8
275
0
570
1
616
2
572
6
288
7
104
7
837
0
517
4
437
7
240
1
533
5
130
0
422
2
367
5

Output for test 10

62435425

Input for test 11

1000
272
362
828
791
617
776
863
175
975
959
282
710
796
206
783
454
363
227
590
238
454
469
362
258
967
839
280
498
229
161
276
474
411
641
518
522
774
406
919
252
923
677
724
748
297
376
283
568
201
203
312
215
514
196
349
226
394
161
967
129
347
689
778
826
338
595
725
434
520
846
934
740
315
593
236
140
297
885
746
707
207
822
366
927
859
527
220
560
390
768
467
800
442
221
936
358
203
896
620
828
400
979
373
801
628
681
606
724
709
100
287
121
808
201
942
132
892
479
939
909
668
125
726
626
640
465
645
203
692
344
599
406
241
546
257
232
885
121
857
837
114
571
875
707
309
835
903
616
726
431
963
753
383
139
632
460
800
853
805
311
890
234
502
570
504
798
870
189
978
865
602
414
948
233
568
831
247
823
245
225
228
240
674
296
780
187
949
913
426
474
686
433
192
552
266
814
844
260
684
192
432
814
701
737
820
686
733
791
351
489
344
458
271
449
850
573
937
875
132
375
357
693
613
474
169
823
821
196
274
871
247
629
378
171
985
195
529
601
904
699
921
107
665
175
435
907
409
306
456
809
834
383
228
294
480
296
473
955
334
547
786
340
983
376
873
160
848
367
823
489
478
410
933
573
319
900
607
578
676
169
576
492
610
128
711
825
718
794
370
628
321
507
455
538
960
712
679
833
699
491
817
686
965
624
410
151
154
502
944
588
947
784
758
549
898
532
490
138
524
502
608
281
182
152
274
790
870
963
494
828
741
508
125
284
256
990
354
848
954
807
325
480
291
885
152
850
244
268
597
730
717
400
583
487
590
403
618
799
781
535
173
293
340
705
118
443
352
867
858
162
800
154
319
111
293
637
197
141
929
719
252
615
198
780
775
794
443
962
764
847
645
474
769
624
589
127
108
971
768
436
290
878
498
871
389
292
181
420
930
809
169
603
548
218
482
572
212
934
656
343
832
355
473
558
413
218
116
333
919
332
581
795
622
524
874
549
569
429
803
259
654
187
107
489
639
587
390
273
469
654
825
877
649
617
136
833
254
233
165
981
728
102
122
239
461
556
183
983
564
303
535
227
438
481
316
468
191
523
509
201
684
272
254
252
940
420
254
168
846
160
334
597
629
289
408
105
681
404
277
366
4
6
0
1
6
8
4
2
5
7
3
6
5
4
6
4
2
1
9
0
2
3
8
8
5
5
9
8
9
4
0
5
2
7
9
7
4
5
3
1
0
3
9
6
3
4
3
4
5
7
9
7
7
3
9
0
4
0
4
1
5
3
1
5
4
8
3
0
8
3
0
4
8
7
5
1
2
8
4
5
5
2
5
4
4
1
1
3
5
0
5
0
4
7
5
4
7
1
8
3
7
1
6
3
6
1
9
1
8
8
8
8
5
7
0
7
9
9
1
5
8
0
1
6
5
7
0
4
2
8
4
8
4
2
0
5
8
3
8
0
0
2
7
5
5
1
6
4
8
9
6
3
2
4
0
1
8
5
4
4
1
2
3
9
3
6
4
2
4
2
6
6
2
3
5
9
2
7
7
2
6
3
1
8
1
6
6
1
8
3
1
0
8
9
3
0
8
6
8
9
1
8
1
6
0
7
6
1
4
6
7
7
4
0
2
9
8
2
1
1
2
4
3
6
3
8
0
1
4
8
3
0
9
7
6
5
9
6
9
0
1
3
4
2
8
2
4
3
2
7
6
8
6
4
3
5
5
3
8
0
8
8
6
6
5
4
3
3
4
1
6
0
0
7
5
9
1
4
5
9
2
3
5
9
5
2
0
5
5
4
6
7
4
7
5
7
7
0
8
5
7
5
0
8
7
1
7
3
7
8
2
7
4
8
6
0
6
6
0
9
9
7
6
2
3
1
8
2
0
9
3
0
1
3
8
1
0
3
1
0
9
5
4
7
1
4
0
5
2
1
8
3
7
1
6
6
6
2
2
0
0
8
6
1
2
9
3
7
1
5
5
5
5
9
0
2
6
7
4
9
2
9
2
6
8
0
5
8
0
9
3
7
8
4
4
5
1
5
9
2
8
4
5
5
3
8
9
0
1
3
7
0
4
7
3
2
8
0
1
1
9
8
9
1
6
3
4
9
8
8
9
6
3
6
8
9
8
0
3
4
8
3
5
6
6
3
0
7
1
0
5
8
6
8
5
4
8
0
0
4
7
0
9
6
2
3
2
2
9
2
1
0
3
1
7
5
6
1
2
6
9
3
7
5
3
3
4
7
5
5
7
9
5
7
0
6
6
5
7
1
4
3
2
6
2
1
0
4
6
8
5
0
9
0
2
4
7
1
3
3
1
5
0
3
7
4
8
6
6
0
3
9
7
9
3
9
8
7
3
1
9
1
1
3
4
7
3
8
0
9
0
0
4
6
6
7
5
0
2
6
7
1
3
7
3
6
1
2
8
6
4
8
9
0
5
5
4
9
0
5
7
1
9
2
3
4
7
7
2
2
0
4
6
7
1
3
2
5
8
4
6
0
6
2
8
6
4
6
1
7
4
2
2
6
1
2
6
0
4
7
1
4
1
3
0
6
8
0
1
2
5
8
5
9
4
3
9
5
2
1
4
0
6
9
5
0
1
6
6
7
1
6
6
9
7
1
2
5
7
9
3
7
4
9
6
1
4
2
6
1
5
5
5
5
5
4
5
8
5
4
7
3
6
7
9
6
2
9
8
0
5
8
9
5
8
2
9
3
0
4
8
7
9
5
6
7
4
3
0
8
9
0
1
0
6
7
4
4
2
1
7
8
7
2
6
1
2
4
8
0
8
6
5
6
6
4
4
2
9
7
9
5
8
9
5
4
7
5
3
7
4
5
5
3
0
0
6
4
1
5
4
6
6
4
5
6
9
9
4
2
0
8
3
8
9
3
2
7
4
4
4
6
6
0
9
8
6
4
9
1
4
8
1
0
7
1
6
9
9
8
7
1
4
2
8
8
0
1
8
5
5
3
5
2
4
2
2
0
3
9
1
2
4
8
9
9
5
8
8
3
2
4
3
5
0
4
0
5
0
8
1
6
1
6
1
8
1
8
5
3
7
9
2
8
7
1
2
6
9
4
4
6
9
7
9
2
1
9
0
6
5
1
9
6
9
3
6
6
8
2
5
6
8
2
6
7
6
8
1
7
9
7
8
8
2
3
6
4
3
7
5
3
8
5
4
2
4
9
1
3
8
9
4
0
8
9
1
9
9
5
6
1
3
6
6
1
6
8
3
0
5
2
7
9
3
8
5
9
0
7
1
4
2
8
9
0
5
4
2
9
5
7
4
7
6
4
0
0
0
0
4
2
1
8
2
5
8
6
0
3
3
6
2
6
1
4
4
7
0
9
0
0
7
4
5
0
6
6
1
6
6
8
0
0
3
9
2
3
0
7
509
249
155
301
710
247
632
738
379
272
840
762
513
613
650
598
902
554
206
629
791
481
406
245
627
266
698
270
601
483
879
605
728
554
601
254
504
339
474
888
351
561
512
831
908
728
403
702
761
574
582
467
186
338
718
162
588
535
710
388
523
326
215
843
146
150
643
415
455
971
558
207
293
958
713
820
235
438
529
942
794
141
870
356
692
532
998
599
770
655
282
501
207
152
371
316
849
224
300
880
208
721
699
693
223
437
259
832
720
706
982
504
970
386
355
195
920
140
558
269
443
691
647
518
768
633
546
338
502
206
577
844
761
798
102
258
635
590
270
388
752
824
394
541
324
185
936
617
954
862
335
146
250
345
731
720
851
204
613
122
528
506
101
852
433
748
273
555
787
689
510
994
123
288
785
497
977
532
102
113
211
984
780
657
364
240
275
570
616
572
288
104
837
517
437
240
533
130
422
367
541
327
503
212
529
539
802
580
676
991
392
169
158
689
697
599
610
649
107
855
324
509
339
305
810
562
508
763
440
954
647
111
252
522
217
900
177
226
223
266
631
463
311
547
971
515
966
646
332
294
812
818
832
370
388
327
550
851
543
507
838
569
679
846
172
449
556
157
442
665
925
835
707
481
985
664
923
319
316
949
367
118
787
820
603
442
143
743
762
106
840
741
712
946
103
308
353
757
340
631
940
577
127
858
975
640
906
339
453
288
585
462
585
818
440
495
652
593
304
769
725
929
647
904
429
718
237
243
956
844
621
798
437
912
251
862
769
938
413
489
458
647
232
110
768
688
340
993
763
487
218
561
933
329
999
378
805
556
392
695
463
121
451
239
345
979
587
567
242
236
894
117
380
563
818
747
214
791
397
600
851
669
275
426
967
982
960
252
849
405
280
893
708
737
350
780
385
470
596
544
285
618
439
413
958
609
677
244
374
791
144
959
197
928
353
643
818
804
580
509
380
520
417
636
593
438
790
764
138
990
370
779
903
396
873
471
673
720
619
870
964
537
617
414
513
600
537
936
199
618
312
779
847
142
616
868
281
595
107
903
436
521
657
590
935
657
667
920
208
394
835
408
124
392
409
145
736
802
414
680
933
621
379
339
441
182
924
891
316
704
825
317
307
518
259
271
939
231
234
555

Output for test 11

158231256

Input for test 12

1000
0
4
0
4
5
5
5
3
3
3
3
2
3
4
5
4
5
0
5
1
0
5
4
5
3
5
3
2
0
0
3
5
4
3
1
2
1
0
5
2
1
3
4
5
1
2
3
5
2
2
4
2
0
3
5
1
2
3
3
0
1
0
5
3
2
1
5
1
1
5
3
1
0
1
0
1
1
3
4
4
4
3
4
2
0
2
3
0
5
0
0
4
5
0
1
1
5
1
0
4
4
3
5
4
2
5
3
4
1
2
2
3
3
4
5
1
0
2
1
3
2
5
1
5
5
1
4
4
0
4
3
4
1
2
0
4
0
3
0
1
3
2
2
0
4
1
5
5
3
0
2
3
0
2
3
3
3
5
0
1
4
1
5
5
1
3
1
1
4
1
0
2
1
2
0
0
1
4
3
4
2
5
0
0
5
1
4
2
0
2
3
4
1
0
2
2
3
1
2
0
3
0
0
2
3
4
2
4
2
5
1
5
3
5
5
2
4
1
3
4
3
4
1
4
5
1
5
0
2
1
4
3
1
4
0
2
3
2
5
5
0
4
2
1
3
2
3
1
1
0
3
3
3
4
5
0
3
4
0
0
3
3
1
3
1
1
5
4
2
2
2
2
0
2
1
3
4
4
2
4
3
0
1
0
2
0
0
4
3
4
2
0
1
3
3
1
5
1
3
5
1
5
5
2
0
0
3
2
4
4
0
5
4
1
3
4
0
3
2
3
0
2
3
5
0
5
0
3
4
2
2
5
5
1
5
5
5
1
2
3
5
2
1
1
2
4
5
2
0
0
5
0
2
0
3
0
3
2
3
1
4
3
5
3
4
4
3
3
5
5
5
4
5
4
5
1
2
3
3
2
1
0
0
1
1
4
2
4
0
3
4
2
1
3
5
3
1
2
5
5
5
2
1
5
0
5
0
2
0
2
3
1
2
3
0
1
5
0
4
3
4
0
5
3
3
5
4
2
5
3
1
3
3
1
2
3
0
0
4
0
0
1
5
1
2
5
0
2
4
4
5
2
4
5
3
5
2
1
2
5
3
1
2
0
2
2
2
2
1
0
0
1
5
5
0
1
3
1
1
1
3
1
1
0
4
4
5
0
3
5
3
0
1
0
5
1
0
5
2
1
2
2
714
3
905
614
739
707
3
998
1
2
2
4
3
4
990
575
817
4
606
890
713
675
910
5
673
1
818
5
537
2
5
723
3
543
773
826
2
1
0
970
3
786
2
5
0
0
525
685
579
635
661
577
1
623
705
3
3
777
1
938
572
2
5
4
1
914
841
5
825
0
503
1
0
984
5
5
0
4
0
825
579
931
723
4
637
4
982
827
549
766
2
2
532
4
1
725
562
4
4
2
641
897
814
950
2
4
587
3
4
3
1
978
900
656
815
5
4
2
650
5
728
666
615
4
0
4
944
832
3
0
716
0
0
523
808
4
5
596
958
5
970
0
638
502
4
3
2
0
3
3
508
5
1
3
4
540
0
948
974
701
2
922
882
887
5
661
862
5
0
4
1
999
3
3
888
722
1
0
5
2
571
779
2
529
685
3
887
0
855
2
823
1
2
0
3
518
5
579
4
5
4
2
2
857
3
931
0
926
798
758
1
520
819
596
3
826
1
922
577
3
812
881
4
991
763
505
4
5
618
561
1
934
812
901
5
1
926
937
764
639
2
559
663
510
0
847
2
596
627
900
0
681
5
1
3
972
2
1
5
849
4
751
968
2
843
839
4
651
4
926
4
1
674
763
0
3
552
744
1
1
731
992
0
1
913
753
572
2
863
568
511
831
607
3
2
926
0
736
5
1
916
0
2
3
706
892
3
527
5
5
3
2
545
3
954
559
559
5
525
986
0
695
5
985
572
901
824
751
845
4
620
915
990
2
1
5
5
3
649
595
633
5
1
3
3
5
1
5
4
2
4
2
707
2
892
1
0
974
947
3
819
650
805
644
0
4
712
673
708
0
4
3
3
3
5
898
0
3
5
865
4
562
4
501
600
2
852
1
647
723
0
3
662
910
5
3
5
2
5
4
2
944
1
846
0
3
682
644
531
0
4
2
0
772
5
981
754
1
3
3
3
805
2
0
748
778
652
546
1
881
985
4
4
884
867
1
811
0
0
865
0
591
4
2
5
775
5
672
988
2
877
4
636
756
0
4
755
3
905
5
0
5
4
5
769
0
3
3
5
515
950
604
2
935
516
0
2
3
971
523
0
0
2
0
540
0
3
941
0
603
838
894
831
518
3
2
3
609
3
919
3
2
4
4
955
849
4
903
4
590
3
2
789
938
1
4
939
1
2
513
899
540
0
4
857
4
3
788
1
0
828
2
589
808
961
885
676
5
613
928
852
5
529
859
789
803
1
5
5
757
2
567
3
5
900
642
922
1
3
668
2
885
3
2
694
723
776
622
566
760
941
964
819
559
739
4
5
721
719
2
5
5
5
597
3
1
751
840
636
615
5
0
642
776
1
767
673
903
847
1
596
2
891
910
601
642
5
5
774
4
1
1
591
5
961
822
967
896
1
3
1
716
740
878
570
5
0
0
0
0
3
982
3
818
675
3
3
525
689
706
1
629
5
919
1
3
5
888
894
696
646
813
841
545
1
781
890
2
5
1
4
978
2
756
4
911
0
807
0
2
5
2
653
765
3
826
4
551
4
642
752
5
1
796
3
1
2
5
799
929
827
688
4
0
0
933
1
2
838
0
2
4
650
4
1
5
529
891
787
791
5
609
832
5
2
0
843
566
641
687
687
504
4
1
5
955
556
1
806
551
872
4
3
953
828
712
686
5
603
916
601
552
927
0
977
1
714
5
2
926
892
825
600
4
817
543
4
815
716
541
2
787
570
0
2
4
705
817
2
3
3
1
633
0
5
3
1
0
4
546
664
501
1
668
1
2
4
3
2
5
547
840
791
1
5
961
4
0
3
608
756
5
4
797
4
5
3
828
676
2
3
623
1
718
881
4
2
592
4
4
615
3
881
4
2
871
2
4
0
3
567
545
2
839
519
666
544
693
5
728
1
4
1
3
2
521
0
3
697
1
4
844
4
0
774
3
2
826
5
0
0
866
895
973
5
554
2
792
928
2
853
687
4
4
3
2
1
5
822
531
4
4
976
5
3
5
3
775
0
0
4
2
4
5
514
5
508
3
661
633
923
5
3
608
1
2
0
741
748
0
564
0
1
5
649
4
4
2
3
719
976
5
0
2
582
859
977
958
0
3
4
4
688
999
798
643
923
630
539
876
960
506
825
557
711
880
5
968
913
992
676
976
0
870
946
4
3
3
5
4
623
686
2
719
2
3
3
631
934
4
0
531
3
3
756
0
538
3
1
687
751
948
875
903
5
935
674
526
576
916
500
0
777
2
829
4
794
666
4
2
1
5
5
1
5
3
2
5
3
5
0
3
4
4
5
1
4
5
2
3
5
3
0
0
1
2
4
1
1
0
1
0
5
1
5
2
4
0
1
5
5
5
1
1
4
0
0
0
5
1
4
5
4
4
3
5
1
5
5
0
5
4
4
2
5
1
4
4
1
3
1
4
3
2
3
1
2
2
5
0
3
3
3
1
0
0
4
5
0
1
5
3
0
1
0
5
2
2
1
2
0
1
4
1
3
0
2
4
2
5
4
5
3
5
4
1
5
2
0
3
2
3
5
0
4
3
5
4
3
5
4
1
0
3
2
1
3
2
5
5
2
1
2
3
0
0
4
4
0
2
5
2
5
2
2
1
5
0
3
3
3
2
2
3
3
5
2
0
1
2
3
1
1
5
4
0
3
0
4
3
2
1
0
1
4
0
0
1
0
4
2
1
0
5
2
3
4
5
1
3
5
2
5
0
5
1
0
2
2
2
5
4
4
3
0
0
4
0
1
2
4
4
4
2
3
0
3
5
3
2
2
2
4
5
1
3
1
1
5
3
2
3
1
4
0
5
4
4
0
5
5
2
3
3
3
4
1
0
3
5
3
4
5
5
3
0
3
4
0
0
1
2
3
1
0
2
0
4
4
4
1
3
5
3
4
2
1
4
0
5
1
1
3
0
1
4
1
2
3
5
0
2
1
2
3
5
4
4
1
2
0
2
4
5
5
2
1
5
4
0
4
5
1
5
0
2
3
5
2
4
4
3
1
3
5
2
2
3
4
3
3
5
3
1
4
3
2
4
2
0
4
4
4
3
1
4
0
2
1
0
1
5
3
0
2
2
2
4
3
1
5
5
4
2
0
2
3
0
4
3
5
0
5
3
4
0
5
2
1
0
2
0
5
0
0
5
0
0
1
4
5
0
3
3
0
1
0
4
0
2
5
5
3
5
2
1
3
5
3
4
5
5
2
2
3
2
1
4
1
2
2
0
0
3
4
0
4
2
2
4
2
2
1
5
5
1
0
2
0
1
5
5
1
1
5
4
2
0
0
3
0
2
1
0
3
3
5
2
5
5
4
2
5
4
5
4
5
0
5
0
5
4
3
0
3
3
3
5
1
3
0
2
4
2
0
1
5
3

Output for test 12

138950820