You have to walk through a forest, which has a shape of a rectangle. The forest is split into a grid of R rows and C columns. You shall enter the forest at a cell (1, 1) and you want to exit the forest from a cell (R, C). You don't want to walk too much, so you make walk from one cell to another only east and south (in the increasing direction of the coordinates). At every cell of the forest, there are either mushrooms you can pick, or boars that will attack you unless you give them mushrooms. Therefore, when you walk through the forest you need to pick mushrooms, so that later you can feed boars. If at some point, you will run out of the mushrooms for the boars, then they will attack you.

You have a map of the forest, so you know precisely how many mushrooms there are in a cell, or how many mushrooms you need to give to the boars, if a cell has boars. Run out of mushrooms means that at a cell the boars have to be fed with more mushrooms than you currently have. E.g., if you have 44 mushrooms, but boars require 45 mushrooms, then they will attack you; if you have 44 mushrooms, and boars require 44 mushrooms, then they will not attack you.

It might not be possible that if you start your walk without any mushrooms, then there is no way of traversing the forest without being attacked. Therefore, you need to buy some mushrooms before you enter the forest. You want to calculate the minimum number of mushrooms that you need to buy.

Input

The first line contains the number of test cases T. T cases follow. Each test case consists of R C (both numbers are <= 500) in the first line followed by the description of the cells in R lines, each containing C integers. Each integer represents the number of mushrooms to pick or to give to the boars; it's always in the interval [-1000, 1000]. Rows are numbered 1 to R from top to bottom and columns are numbered 1 to C from left to right. Cells with < 0 number of mushrooms contain boars, and represent the number of mushrooms with which you need to feed the boars; cells with >= 0 number of mushrooms just say how many mushrooms there are. You may assume that at the cell (1, 1) the number of mushrooms is always 0.

Output

Output T lines, one for each case containing the minimum number of mushrooms you need to buy walk from cell (1, 1) to cell (R, C) without being attacked by the boars.

Example

Input:
3
2 3
0 1 -3
1 -2 0
2 2
0 1
2 0
3 4
0 -2 -3 1
-1 4 0 -2
1 -2 -3 0 

Output:
1
0
1