2
1 2 3
3 7 1
3 4 5
3
1 2 3
3 7 1
2 1 2
3 4 5
3
2 0 0
0 2 0
2 2 0
12 13 0
3
5000 0 0
4873 7123 0
1903 0 0
0 0 1
3
5000 0 0
4873 7123 0
1903 0 0
8732 9712 0
3
1 0 0
0 1 0
1123 123 0
1231 31 1123
30
1 1 1
1 1 2
2 2 3
3 3 5
5 5 8
8 8 13
13 13 21
21 21 34
34 34 55
55 55 89
89 89 144
10 10 16
6 6 10
2 2 2
2 2 4
3 3 3
3 3 6
1000 1000 1000
12 12 12
13 13 13
14 14 14
10 10 16
20 20 32
40 40 64
6 6 2
16 16 18
32 32 36
64 64 72
12 12 4
7 7 7
999 987 934
30
1 1 1
1 1 2
2 2 3
3 3 5
5 5 8
8 8 13
13 13 21
20 21 34
34 34 55
55 55 89
89 89 144
10 10 16
6 6 10
2 2 2
2 2 4
3 3 3
3 3 6
1000 1000 1000
12 12 12
13 13 13
14 14 14
10 10 16
20 20 32
40 40 64
6 6 2
16 16 18
32 32 36
64 64 72
12 12 4
7 7 7
16 16 9
0