Maximum Coins Collection

You are given an \(N \times N\) grid where each cell contains a certain number of coins. The task is to determine the maximum number of coins one can collect by starting at the top-left corner and moving to the bottom-right corner of the grid.

You can only move either to the right or down at any step. Formally, if the grid is denoted by \(grid\) and you define a dynamic programming state \(dp[i][j]\) as the maximum coins collectable to reach cell \((i, j)\), then the recurrence is given by:

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

Your program should read input from standard input (stdin) and output the maximum coins for each test case to standard output (stdout), with each answer on a separate line.

inputFormat

The first line contains an integer \(T\), representing the number of test cases.

For each test case, the first line contains an integer \(N\) (the size of the grid). This is followed by \(N\) lines, each containing \(N\) space-separated integers representing the coin values in the grid.

Input is read from stdin.

outputFormat

For each test case, output the maximum number of coins that can be collected on a new line. The output is printed to stdout.

## sample

1
3
1 2 3
4 5 6
7 8 9

29

</p>