input:

5501
8 104
5 2 3
6 2 4
5 2 3
6 2 9
8 2 4
2 1 3
7 2 4
8 2 8
1 290
3 1 1
12 12
6 1 2
1 2 2
1 1 2
1 2 4
6 1 1
1 2 5
6 1 4
4 1 4
6 2 4
6 2 5
4 2 5
4 1 4
5 334
1 1 4
1 2 3
4 2 1
5 1 1
2 1 2
13 218
5 2 3
5 1 4
1 2 1
1 2 5
3 2 2
1 1 3
4 2 2
1 2 5
2 2 1
2 1 5
3 2 1
5 2 1
1 1 4
10 260
7 2 1
5 1 1
5 2 4
6 1 6...

output:

9
1
23
4
5
7
1
3
10
6
1
11
4
9
17
6
4
1
8
5
5
7
1
3
23
6
3
3
2
2
2
3
9
1
5
6
13
11
147
8
12
2
13
7
8
6
5
5
1
7
3
14
10
17
7
10
8
1
4
2
3
9
1
5
2
9
1
6
7
7
6
10
18
8
10
13
10
9
2
16
3
5
9
3
6
5
3
2
6
1
3
2
2
1
6
11
6
3
4
8
9
9
2
6
1
2
6
7
5
2
5
25
8
1
2
3
4
9
3
4
6
5
9
7
1
7
3
7
3
2
2
8
7
3
5
9
8
10
...

result:

wrong answer 9th lines differ - expected: '9', found: '10'