Maximum Coins Collection

You are given a grid of integers where each cell contains some coins. Your task is to determine the maximum number of coins you can collect starting from the top-left corner (cell (1,1)) and reaching the bottom-right corner (cell (M,N)). You can only move either right or down at any point in time.

The problem can be solved using dynamic programming. Let \(dp[i][j]\) be the maximum number of coins collected when reaching cell \((i,j)\). The recurrence relation is given by:

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

For the starting cell \((1,1)\), \(dp[1][1] = grid[1][1]\). Your task is to compute \(dp[M][N]\) for each test case.

inputFormat

The first line of input contains an integer T representing the number of test cases. Each test case is described as follows:

1. The first line of each test case contains two space-separated integers M and N, representing the number of rows and columns in the grid respectively.
2. This is followed by M lines, each containing N space-separated integers indicating the number of coins in each cell of the grid.

All inputs are read from standard input (stdin).

outputFormat

For each test case, output a single integer on a new line representing the maximum number of coins that can be collected by following an optimal path from the top-left to the bottom-right corner of the grid. The result for all test cases should be printed to standard output (stdout).

## sample

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

10

</p>