Maximum Treasure Collection

Emily is on a quest to collect treasures laid out on an N x N grid. Each cell of the grid contains a certain number of treasure points. Starting at the top-left corner, she can only move either right or down. Your task is to compute the maximum treasure points Emily can accumulate when she reaches the bottom-right corner.

The dynamic programming recurrence used to solve this problem is given by:
(dp[i][j] = \text{grid}[i][j] + \max(dp[i-1][j],; dp[i][j-1]))
with the base condition (dp[0][0] = \text{grid}[0][0]) and appropriate initialization for the first row and first column.

inputFormat

The input is read from stdin with the following format:

1. The first line contains an integer (T), the number of test cases.
   
2. For each test case:
   
   1. The first line contains an integer \(N\), representing the size of the grid.
   2. The next \(N\) lines each contain \(N\) space-separated integers, representing the treasure points in the grid.

outputFormat

For each test case, output the maximum treasure points that can be collected. Each result should be printed on its own line to stdout.## sample

1
3
1 3 1
1 5 1
4 2 1

12