Captain Jack Sparrow was taken to the Davy Jones Locker along with The Black Pearl by the Kraken. Will and Elizabeth have set sail along with Barbossa towards the Locker at the World's End to rescue Jack. They can only go south or east on their route to the Locker.

They also find many treasures as well as dangerous creatures on their way. Each treasure increases the supply of resources with them while the creatures take away a few of the resources from the ship. If at any point of time, the resources in the ship become zero or less, the ship drowns and they cannot reach the Locker.

Currently, the ship is at position A[1][1]. They know from the Navigational Charts that the Davy Jones Locker is situated at location A[N][M]. Each cell of a N x M matrix represents the amount of resources that may be increased or decreased on the ship.

Captain Barbossa, who is in control of the ship, can figure out the best path to reach the locker. But he doesn't know the mathematics needed to calculate what intial supply of resources they will need. So he assigns this task to Will and Elizabeth. Since they are also not able to calculate it, they turn to you for help.

Determine the minimum initial supply of resources that they need to take along with them so that they can rescue Jack from the Locker.

Input

The first line contains T, the number of test cases. T test cases follow.

The first line of each test case contains two integers N and M

The next N lines contain M space separated integers.

A positive integer indicates a Treasure while a negative integer indicates a creature.

It is guaranteed that there will be no treasure or creature at locations (1,1) and (N,M).

Output

Print the intital supply of resources needed for each test case in a new line.

Constraints

1 <= T <= 100

2 <= N,M <= 500

-1000 <= A[i][j] <= 1000

Warning

Large I/O files. Use printf/scanf instead of cin/cout