Queen's Energy Collection

You are given a grid representing Byteland's garden, where each cell contains an integer value corresponding to the energy of a flower. The Queen starts from any cell in the first row. She moves downwards row by row and in each move, she is allowed to go directly below, diagonally left below, or diagonally right below. Your task is to compute the maximum energy that the Queen can collect by the time she reaches the bottom row.

Note: It is guaranteed that in each move the Queen stays within the bounds of the grid.

---

Problem Formula

If the energy at cell (i, j) is denoted by \(g_{i,j}\) and the maximum energy to reach cell (i, j) is \(dp_{i,j}\), then the recurrence is:

[ dp_{i,j} = g_{i,j} + \max \begin{cases} dp_{i-1,j} \ \text{if } j > 0: dp_{i-1,j-1} \ \text{if } j < M-1: dp_{i-1,j+1} \end{cases} ]

The answer is \(\max_{0 \leq j < M} dp_{N-1,j}\) for each test case.

inputFormat

The first line contains a single integer \(T\) indicating the number of test cases.

For each test case:

• The first line contains two integers \(N\) and \(M\), representing the number of rows and columns in the garden respectively.
• The following \(N\) lines each contain \(M\) space-separated integers. Each integer represents the energy value in the corresponding cell of the garden.

outputFormat

For each test case, output a single integer in a new line indicating the maximum energy that the Queen can collect.

## sample

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

18

</p>