Maximum Path Sum in a Grid

You are given one or more square grids. Each grid contains non-negative integers. Your task is to compute the maximum sum achievable when moving from the top-left cell to the bottom-right cell of the grid, following only right or down moves.

The problem can be formalized as follows: given a grid \(G\) of size \(n \times n\), you want to determine the maximum sum along a path starting at \(G_{0,0}\) and ending at \(G_{n-1,n-1}\), where at each step you may only move either right or down. The optimal substructure naturally leads to a dynamic programming solution.

Input Format: The first line of input contains an integer \(T\) denoting the number of test cases. For each test case, the first line contains an integer \(n\) representing the size of the grid. The next \(n\) lines each contain \(n\) space-separated integers representing the grid.

Output Format: For each test case, print a single line containing the maximum path sum from the top-left to the bottom-right of the grid.

inputFormat

stdin: The input begins with an integer \(T\) representing the number of test cases. For each test case:

• The first line contains an integer \(n\) \( (1 \le n \le 100) \) which is the size of the square grid.
• The next \(n\) lines contain \(n\) space-separated integers each.

All integers in the grid are non-negative and do not exceed \(10^9\).

outputFormat

stdout: For each test case, output one line containing the maximum sum reachable from the top-left to the bottom-right corner following the allowed moves.

## sample

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

29
4

</p>