Minimum Path Sum in a Matrix

Given a square matrix of order \(N \times N\), where \(N\) is a positive integer, find the minimum path sum from the top-left cell to the bottom-right cell. You can only move either right or down at each step. The objective is to compute the sum of the values along the path such that the total sum is minimized.

The problem can be formulated using dynamic programming. Let \(dp[i][j]\) represent the minimum path sum to reach cell \((i, j)\) starting from \((0,0)\). The recurrence relation is given by:

[ \begin{aligned} dp[i][j] &= \min(dp[i-1][j],; dp[i][j-1]) + matrix[i][j] \ dp[0][j] &= dp[0][j-1] + matrix[0][j] \ dp[i][0] &= dp[i-1][0] + matrix[i][0] \end{aligned} ]

Implement the solution to read input from standard input and write the answer to standard output.

inputFormat

The first line of the input contains a single integer \(T\) denoting the number of test cases. Each test case begins with an integer \(N\) — the dimension of the square matrix. The next \(N\) lines contain \(N\) space-separated integers each, representing the rows of the matrix.

outputFormat

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

## sample

2
2
1 2
3 4
3
1 2 3
4 5 6
7 8 9

7
21

</p>