Minimum Path Sum on a Grid

You are given a square grid of size n × n where each cell contains a positive integer. Starting from the top-left corner, your task is to find a path to the bottom-right corner such that the sum of the values along the path is minimized. You can only move either right or down at any point in time.

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

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

with the base condition dp[0][0] = grid[0][0]. Your solution must calculate the minimum path sum following these rules.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains an integer T, the number of test cases.
2. For each test case:
• The first line contains an integer n, the size of the grid.
• The next n lines each contain n space-separated integers representing the grid.

outputFormat

For each test case, output the minimum path sum from the top-left corner to the bottom-right corner on a new line to stdout.

## sample

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

7
3

</p>