Maximum Gold Collection

You are given a grid of size \( n \times m \) where each cell contains a certain amount of gold. Your task is to determine the maximum amount of gold you can collect while moving from the leftmost column to the rightmost column.

At each step, from cell \( (i, j) \), you can move to:

• Right: \( (i, j+1) \)
• Right-up: \( (i-1, j+1) \)
• Right-down: \( (i+1, j+1) \)

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

[ \text{dp}[i][j] = \text{grid}[i][j] + \max{\text{dp}[i][j+1],; \text{dp}[i-1][j+1],; \text{dp}[i+1][j+1]}]

You need to compute this value for each test case. A test case consists of a grid where you start from any row in the leftmost column and try to collect the maximum gold by following the allowed movements until the rightmost column is reached.

inputFormat

The first line of the input contains an integer \( T \) denoting the number of test cases. For each test case:

1. The first line contains two space-separated integers \( n \) and \( m \), representing the number of rows and columns of the grid.
2. The following \( n \) lines each contain \( m \) space-separated integers representing the gold values in each cell of the grid.

outputFormat

For each test case, output a single line containing one integer: the maximum amount of gold that can be collected from the leftmost to the rightmost column.

## sample

1
3 3
1 3 1
3 2 1
4 0 6

12

</p>