Max Energy Collection in a Grid

You are given a grid of non-negative integers with dimensions \(M \times N\). Starting from the top-left cell, you can only move either right or down at each step, and you want to reach the bottom-right cell while collecting as much energy as possible. The energy collected is the sum of the numbers along the chosen path.

The recurrence relation to solve this problem is given by:

[ dp[i][j] = grid[i][j] + \max(dp[i-1][j],, dp[i][j-1]) ]

with the base case \(dp[0][0] = grid[0][0]\). For the first row and the first column, you only have one direction to come from. You need to handle multiple test cases as provided in the input.

Read the input from standard input and print the answers for each test case to standard output.

inputFormat

The input begins with an integer \(T\) representing the number of test cases. For each test case:

• The first line contains two integers \(M\) and \(N\), denoting the dimensions of the grid.
• The following \(M\) lines each contain \(N\) integers, representing the energy values in the grid.

All input should be read from standard input.

outputFormat

For each test case, output a single line with the maximum energy that can be collected when moving from the top-left to the bottom-right of the grid.

Output all answers to standard output, each on a new line.

## sample

2
3 3
1 3 1
1 5 1
4 2 1
2 2
1 2
1 3

12
6

</p>