Maximum Gold Collection from Gold Mine

Imagine a gold mine represented by a 2D matrix with dimensions 'N' by 'M', where 'N' is the number of rows and 'M' is the number of columns. Each cell in this matrix contains a positive integer representing the amount of gold in kilograms available at that position.

The miner starts at any row of the first column of the gold mine. The only permissible movements for the miner from any given cell are:

• Move directly to the right
• Move to the right and up diagonally
• Move to the right and down diagonally

Your task is to determine the maximum amount of gold the miner can collect by the time he reaches the last column.

Input:

The first line contains an integer 'T’, which denotes the number of test cases. The subsequent '2 * T' lines describe the test cases as follows: For each test case, the first line contains two space-separated integers 'N' and 'M', representing the dimensions of the gold mine. The second line contains 'N * M' space-separated integers, representing the gold mine by row-wise traversal.

Output:

For each test case, output a single integer representing the maximum amount of gold collected. Each result should be printed on a new line.

Example:

Input:

2
3 3
1 3 3 2 1 4 0 6 4
4 4
1 3 1 5 2 2 4 1 5 0 2 3 0 6 1 2

Output:

12
16

Explanation:

In the first test case, the path (2 → 3 → 4) yields the maximum gold (3 + 4 + 5 = 12). In the second test case, the path (3 → 4 → 6 → 3) yields the maximum gold (3 + 4 + 6 + 3 = 16).

Constraints:

• 1 <= T <= 10
• 1 <= N <= 100
• 1 <= M <= 100
• 0 <= gold at each cell <= 10^5