Maximize Flower Significance

In this problem, you are given a garden represented by a series of rows, where each row contains three flowers. Each flower has a significance value. Your task is to select exactly one flower from each row such that no two consecutive rows use the flower from the same column, and the total significance value is maximized.

More formally, for each test case you are given an integer (N) and a matrix (A) of size (N \times 3) where (A_{i,j}) represents the significance value of the (j^{th}) flower in the (i^{th}) row. You need to choose a sequence (c_1, c_2, \dots, c_N) with (c_i \in {1,2,3}) such that (c_i \neq c_{i+1}) for (1 \le i < N) and maximize the sum (\sum_{i=1}^{N} A_{i, c_i}).

For example, consider a single test case with (N = 3) and a matrix: [ \begin{bmatrix} 3 & 2 & 5 \ 4 & 6 & 3 \ 7 & 8 & 9 \end{bmatrix} ] One possible selection is to choose 5 from the first row, 6 from the second row, and 9 from the third row, accumulating a total significance value of 20. Your solution must correctly compute such maximum values for all test cases.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer (T) which denotes the number of test cases.
• For each test case:
  • The first line contains an integer (N) (the number of rows in the garden).
  • This is followed by (N) lines, each containing three space‐separated integers representing the significance values of the three flowers in that row.

For example:

1 3 3 2 5 4 6 3 7 8 9

outputFormat

For each test case, output a single line containing the maximum total significance value that can be obtained by selecting one flower from each row under the given constraint.## sample

1
3
3 2 5
4 6 3
7 8 9

20