Gold Mine Problem Statement

You are provided with a gold mine, represented as a 2-dimensional matrix of size N x M with N rows and M columns. Each cell in this matrix contains a positive integer representing the amount of gold (in kgs) at that location.

Initially, the miner is positioned at the first column in any row. From any given cell, the miner can travel in either of the following directions: right, right-up, or right-down.

Your task is to determine the maximum amount of gold that the miner can collect by only moving in the allowed directions.

Input:

The first line contains an integer 'T', denoting the number of test cases.
Each test case consists of two lines:
1. The first line contains two space-separated integers, 'N' and 'M', which represent the dimensions of the gold mine.
2. The second line contains N * M space-separated integers that form the gold mine matrix.

Output:

For each test case, output an integer 'X' indicating the maximum amount of gold that can be collected.
Print the output for each test case on a new line.

Example:

T = 1

N = 3, M = 3
Gold Mine Matrix:

1 3 1
2 1 4
0 6 4

The output will be:

12

Constraints:

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 100
• 1 ≤ M ≤ 100
• 0 ≤ gold in each cell ≤ 10⁵

Time Limit: 1 second

Note:

No need to print the output; just implement the function logic to achieve the solution.