Maximum Path Sum in a Matrix

Given an N*M matrix filled with integer numbers, determine the maximum sum that can be obtained from a path starting from any cell in the first row to any cell in the last row.

You can move from a cell in the current row to another cell directly below, or diagonally below left or right.

Input:

The first line contains an integer 'T', the number of test cases. For each test case:
The first line contains two integers 'N' and 'M', representing the matrix dimensions.
The next 'N' lines contain 'M' space-separated integers representing the matrix elements.

Output:

For each test case, print the maximum sum that can be obtained by following a path as described. Output a separate line for each test case.

Example:

Input:
2
2 3
1 2 3
4 5 6
2 2
9 10
-1 -2

Output:
11
10

Constraints:

• 1 <= T <= 50
• 1 <= N <= 100
• 1 <= M <= 100
• -10⁴ <= matrix[i][j] <= 10⁴
• Time Limit: 1 second

Note:

You do not need to print anything. It has already been taken care of.