Input:
4
4
1 3 5
2 4 6
7 8 9
8 10 1
3
1 4 4
4 7 5
3 4 7
5
1 5 5
2 4 3
3 6 10
6 8 3
6 9 7
19
5 86 53
3 98 28
46 78 75
27 56 35
1 86 30
7 72 23
57 78 51
15 92 5
17 67 36
17 56 19
3 78 25
11 78 46
1 51 93
5 57 40
7 95 76
21 92 43
15 67 69
15 18 98
27 72 43
Outout:
15
7
15
208