2
8 30
2 2 22
2 4 12
4 1 8
1 8 2
8 6 12
6 2 2
2 2 2
2 2 2
5 6 1
6 6 3
6 2 1
6 1 1
1 2 1
5 2 1
6 4 3
6 4 2
4 8 1
5 3 2
2 2 3
7 2 1
2 6 2
2 5 2
8 2 2
8 1 3
6 8 4
8 5 2
8 5 3
2 6 3
4 2 3
2 8 6
2 6
10 50
6 6 2
6 9 40
9 1 32
1 7 2
7 8 44
8 2 32
2 2 2
4 7 6
7 2 2
4 2 1
8 2 1
3 10 4
8 2 2
4 10 10
2 2 1
3 2 2
6 4 5
4 4 2
2 6 3
2 2 2
2 9 7
8 2 2
2 2 3
10 2 3
8 10 7
2 2 1
8 6 1
4 4 2
8 6 1
8 8 1
8 2 1
4 6 1
6 2 3
2 2 3
6 2 2
2 6 2
2 2 2
3 2 3
2 2 3
2 8 4
4 6 2
6 6 2
2 10 9
10 7 1
1 2 1
2 7 10
2 2 1
4 10 8
2 6 1
4 2 1
6 2