Minimum Energy on the Magical Belt

You are given a square grid representing a magical belt. Each cell in the grid has an integer energy cost. Starting from the top‐left corner of the belt, you need to find a path to the bottom‐right corner with the minimum total energy cost. You can only move either right or down at any step.

Mathematically, let \( A[i][j] \) represent the energy cost at cell \( (i,j) \) (with 0-indexing). Define \( dp[i][j] \) as the minimum energy required to reach cell \( (i,j) \). The recurrence is given by:

[ dp[i][j] = \min\begin{cases} dp[i-1][j] \ dp[i][j-1] \end{cases} + A[i][j], \quad (i,j) \neq (0,0) ]

with the initialization \( dp[0][0] = A[0][0] \). Output the value \( dp[n-1][n-1] \) for each test case.

Input Format: The first line contains an integer \( t \) specifying the number of test cases. For each test case, the first line contains an integer \( n \) (the dimension of the square grid), followed by \( n \) lines each containing \( n \) space-separated integers.

Output Format: For each test case, output a single integer on a new line representing the minimum energy required.

inputFormat

The input is read from standard input (stdin) and has the following structure:

1. The first line contains an integer \( t \) representing the number of test cases.
2. For each test case:
• The first line contains \( n \) (the size of the grid).
• Next \( n \) lines each contain \( n \) integers separated by spaces, representing the energy costs in each row of the grid.

outputFormat

For each test case, output the minimum total energy required to traverse the grid from the top-left corner to the bottom-right corner. Each result should be printed on a new line to standard output (stdout).

## sample

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

21
7

</p>