3
2 4
1 1
2 1 2 0
1 1 2
1 2 3
2 1 2 0
3 5
1 2 3
2 1 2 1 1 2
2 1 2 1 1 3
2 1 2 1 2 3
1 1 6
2 1 2 1 1 2
6 10
1 1 1 1 9 2
2 1 6 4 1 2 1 3 1 4 1 6
1 1 4
1 2 10
1 3 8
2 3 2 1 2 3
1 4 100000000
2 2 6 0
1 6 9
2 2 6 1 3 1
2 3 5 3 3 5 1 3 1 5