Maximum Magical Power

Leoric is trapped in a mysterious dungeon represented as a grid with n rows and m columns. Each cell in the grid contains a certain amount of magical power. Starting at the top-left corner, Leoric can only move either to the right or downward. Your task is to help Leoric determine the maximum magical power he can collect when he reaches the bottom-right cell.

The solution is based on dynamic programming. Let \(dp[i][j]\) be the maximum power collectable at cell \((i,j)\). The recurrence relation is:

\(dp[i][j] = \max(dp[i-1][j],\, dp[i][j-1]) + a_{i,j}\)

with the initial condition \(dp[0][0] = a_{1,1}\).

inputFormat

The input begins with an integer t (1 ≤ t ≤ 100), the number of test cases. For each test case:

• The first line contains two integers n and m (1 ≤ n, m ≤ 100), representing the number of rows and columns of the grid.
• This is followed by n lines, each containing m space-separated integers, which represent the magical power available in each cell of the grid.

outputFormat

For each test case, output a single line containing the maximum magical power Leoric can accumulate by the time he reaches the bottom-right corner of the grid.

## sample

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

29
8
1

</p>