Minimum Path Sum in a Grid

You are given an (N \times N) grid filled with non-negative integers. Your task is to determine the minimum cost to reach the bottom-right corner from the top-left corner, moving only to the right or down.

Formally, for a grid (G) with indices ranging from (0) to (N-1), find the minimum cost path from (G(0,0)) to (G(N-1,N-1)) such that every step is either a move to (G(i+1,j)) or (G(i,j+1)).

You may assume that (1 \le N \le 500).

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains an integer (T), the number of test cases.
• For each test case:
  • The first line contains an integer (N), the size of the grid.
  • The next (N) lines each contain (N) space-separated integers representing the grid.

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

outputFormat

For each test case, output a single line to standard output (stdout) containing one integer which is the minimum path cost from the top-left to the bottom-right of the grid.## sample

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

21
3