Your friend, John, is a pirate. One day, he found a map marking the treasures of the sea, which described as following:
1. Like most maps in the world, the east is on the right-hand side of map.
2. The map splits the sea into grids, separated by vertical and horizontal lines.
3. For each grid, there is a non-negative number presenting how many treasures are there on the islands in the grid.
4. Any regions out of the map contain no treasure.
In this season, the wind blows from the north to the south. With the help of wind, John will drive his boat from the north of sea to the south. The boat can sail to east or west, but there are some limitations.
John will start his journey from any grids in the north side of the sea in map (any grid on the top of map). After gathering the treasures in the grid, there are 3 directions he can choose:
1. South. He will go down on the map.
2. Southeast. He will reach the grid on the right of choice 1.
3. Southwest. He will reach the grid on the left of choice 1.
As described above, there is no way to sail east, west, or north. After John sail out of the south grids on the grid, his journey will end.
Since John promised you to share half of the treasures he gets in the journey, you are to find out how may treasures you and John can get most if he chooses the path carefully.
There will be multiple cases in the input.
The first line contains a positive integer T, T≦10, which denotes the number of cases.
The next line contains 2 positive integers, R and C (≦100), denoting the size of map for rows and columns. There are R lines following, denoting the rows from north to south, and each row contains C integers, which are the value of treasures in that grid(≦10000).
Values will be separated with spaces.
For each case, output a line containing one integer denoting the maximum value of treasures John and you may get.