Minimum Cost Path in a Matrix

You are given a matrix of non-negative integers. Your task is to find the minimum cost path from the top-left cell to the bottom-right cell. Allowed moves are only to the right or downward. The problem can be formulated using dynamic programming. In particular, let \(dp[i][j]\) represent the minimum cost to reach cell \((i,j)\). Then, for \(i,j \ge 1\), the recurrence is given by:

\(dp[i][j] = matrix[i][j] + \min(dp[i-1][j],\; dp[i][j-1])\)

with the base cases defined by the first row and first column. Solve the problem for each of the given test cases.

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 number of rows and columns respectively. This is followed by \(M\) lines, each containing \(N\) space-separated integers representing the matrix.

outputFormat

For each test case, output a single line containing the minimum cost path from the top-left cell to the bottom-right cell.

## sample

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

7
4

</p>