Minimum Path Sum

You are given an m (\times) n grid filled with non-negative integers. Your task is to find the minimum path sum from the top-left corner to the bottom-right corner of the grid. You can only move either down or right at any point in time. For each test case, print the computed minimum path sum as the output.

For example, given the grid: [ \begin{matrix} 1 & 3 & 1 \ 1 & 5 & 1 \ 4 & 2 & 1 \end{matrix} ] The minimum path sum is (7), corresponding to the path (1 \rightarrow 3 \rightarrow 1 \rightarrow 1 \rightarrow 1).

inputFormat

The input begins with an integer (t) representing the number of test cases. For each test case, the first line contains two integers (m) and (n) denoting the number of rows and columns of the grid. This is followed by (m) lines, each containing (n) space-separated non-negative integers representing the grid values.

outputFormat

For each test case, output a single integer on a new line — the minimum path sum from the top-left corner to the bottom-right corner of the grid.## sample

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

7