Largest Zigzag Sequence Problem

Given a square matrix MAT of dimensions N x N, define a 'zigzag' sequence as one that starts from the top row and ends at the bottom row, with the requirement that no two consecutive elements of the sequence are from the same column.

Your task is to determine the maximum possible sum of any zigzag sequence in this matrix.

Input:

Integer T, the number of test cases.
For each test case:
Integer N.
N lines each with N space-separated integers MAT[i][j].

Output:

For each test case, output the maximum sum of a zigzag sequence, each result on a new line.

Example:

Input:
T = 1
N = 3
MAT = [[1, 2, 3],
       [4, 5, 6],
       [7, 8, 9]]
Output:
15

Explanation: The sequence could be 3 (from row 1), 6 (from row 2), 9 (from row 3), resulting in a total sum of 18.

Constraints:

• 1 <= T <= 10
• 1 <= N <= 100
• 1 <= MAT[i][j] <= 1000