Minimum Path Cost in a Grid

You are given a square grid of size \(n \times n\) where each cell contains a non-negative cost. Your task is to determine the minimum cost required to travel from the top-left cell (position (0, 0)) to the bottom-right cell (position (n-1, n-1)).

You are allowed to move in four directions: up, down, left, and right. The cost of a path is the sum of the costs of all cells visited (including the starting and ending cells). It is guaranteed that a path always exists.

Note: The grid is provided in each test case, and you must process multiple test cases from the standard input.

inputFormat

The input begins with an integer \(T\) representing the number of test cases. Each test case is formatted as follows:

• An integer \(n\) representing the size of the grid (number of rows and columns).
• \(n\) lines follow, each containing \(n\) space-separated integers representing the cost values in the grid.

For example:

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

outputFormat

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

For the sample above, the output should be:

7
7

## sample

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

7
7
1

</p>