Minimum Path Sum

Source of the problem: LeetCode

Given a r-by-c grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Input

The first number, n, indicates the number of test cases, followed by the n test cases. Each test case begins with a line of two numbers, r and c, which indicate the number of rows and the number of columns for the test case; then the r-by-c array (grid) of numbers are listed.

Output

For each test case, find a path from top left to bottom right which minimizes the sum of all numbers along its path, and please print the minimum sum in a single line.

2
3 3
1 3 1
1 5 1
4 2 1
4 4
1 1 1 2
2 1 1 2
2 1 1 1
2 1 1 1

7
7