input:

5
6 1 9 8 5
3 1 1 5 5
5
8 7 4 3 6
3 4 3 1 5
5
5 1 4 1 2
5 2 3 0 5
5
7 4 7 5 2
5 3 3 4 1
5
4 1 2 5 5
2 4 1 5 5
5
6 8 4 6 9
4 4 3 3 1
5
3 10 0 6 0
3 1 4 1 3
5
0 6 5 9 10
4 1 5 1 1
5
0 8 1 5 6
0 0 1 4 4
5
4 7 8 8 2
2 1 1 4 1
5
0 10 3 3 8
3 4 3 4 5
5
10 5 9 10 9
4 4 0 2 4
5
8 0 1 7 6
5 3 3 3 3
5
0 6 9 5...

output:

15
16
12
16
17
15
12
12
9
9
19
14
15
7
16
13
15
9
10
18
11
11
12
14
11
8
12
10
8
12
17
13
20
6
16
17
8
14
17
5
12
11
16
15
12
5
12
13
12
16
13
12
1
14
13
8
12
10
11
14
4
5
15
11
12
7
10
9
13
13
9
16
8
12
8
13
14
18
5
13
16
13
10
16
20
12
18
8
12
11
12
18
5
15
13
12
5
14
15
7
17
12
7
15
16
9
16
16
15...

result: