Minimum Path Sum in Grid

You are given a grid consisting of non-negative integers. Your task is to find the minimum path sum from the top-left corner (0,0) to the bottom-right corner (n-1,m-1). You can move either right or down at any step.

The recurrence relation for the dynamic programming solution is given by:

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

for all valid indices i and j with appropriate initialization for the first row and first column. The answer for each test case is the value at dp[n-1][m-1].

inputFormat

The first line of input contains an integer T representing the number of test cases. For each test case:

• The first line contains two integers n and m separated by space, representing the number of rows and columns of the grid.
• This is followed by n lines, each containing m integers separated by spaces, representing the rows of the grid.

outputFormat

For each test case, output a single integer which is the minimum path sum from the top-left to the bottom-right corner. Each result should be printed on a new line.

## sample

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

7
3

</p>