3
1 6 2
1 3 5
5 4 3
3
3 2 1
6 5 4
9 8 7
3
1 23 4
12 3 4
1 2 34
6
1 1 1 1000000000 1000000000 1000000000
1000000000 1000000000 1000000000 1 1 1
1 1 1 2 2 2

5
0
36
2999999997