Sagar just got placed for 18 lakhs at a multinational company. He decides to go all SAW on you and says "I want to play a game". But don't you worry, this game has nothing to do with cutting your body parts. This game benefits you only.

Since Sagar has so much money, he has decided to give some off. He lays various coins on an n X m board, with different number of coins on each cell. He tells you that if you can take the maximum number of coins off the board, you can keep them. Though there is a catch to it. He restricts your movement to down, diagonally left or diagonally right in the downward direction of the cell from which you have taken coins most recently.

I hope you play to win. Collect the maximum number of coins.

Input

The first line contains a single integer t (lies in 1 to 100, both inclusive) — the number of test cases. Next line contains n & m. Next n lines contain m numbers which represent the number of coins placed on specific cell. The same continues for t test cases.

Output

The maximum number of coins you can take off from the board under the given conditions

Sample Input

1

3 3

5 3 2

9 7 5

1 2 10

Sample Output

22

Explanation