Minimum Path Sum

You are given a grid with R rows and C columns. Each cell of the grid contains an integer value. Your task is to find the minimum sum path from the top-left corner to the bottom-right corner of the grid. You can only move either to the right or down at any point in time.

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

[ dp[i][j] = grid[i][j] + \min(dp[i-1][j],; dp[i][j-1]) ]

Given multiple test cases in a single input, process each grid and output the minimum sum for each test case on a new line.

inputFormat

The input is read from standard input (stdin). The first line contains an integer T representing the number of test cases. Each test case begins with a line containing two space-separated integers R and C, indicating the number of rows and columns in the grid. This is followed by R lines, each containing C space-separated integers representing the grid values.

outputFormat

For each test case, output a single integer — the minimum sum path from the top-left to the bottom-right corner of the grid. Each answer must be written to standard output (stdout) on a new line.

## sample

1
2 2
1 2
3 4

7

</p>