Given a matrix M of size n*m, find the maximum path sum.

Here, a valid path starts at any element in the first row and ends at any element on the last row.
Every step we can move one cell in one of three directions:

1. Down
2. Diagonally to left
3. Diagonally to right

Example

M[][]: 12 22  5  0 20 18
        0  2  5 25 18 17
       12 10  5  4  2  1
        3  8  2 20 10  8
Result: 70
Explanation: Maximum path: 20 → 25 → 5 → 20

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of test cases.
For each test case, the input has the following lines:

• Two space-separated integers ‘n’ and ‘m’ denoting the size of the matrix M.
• Next n lines containing m space-separated integers denoting the matrix.

Output Format

For each test case, the output contains a line with one integer denoting the maximum path sum.

Sample Input

2
4 6
12 22 5 0 20 18
0 2 5 25 18 17
12 10 5 4 2 1
3 8 2 20 10 8
2 2
3 8
7 3

Expected Output

70
15

Constraints

1 <= T <= 10
1 <= n, m <= 500
0 <= Mij <= 103