Diablo 3 is coming now. But because of the login problem at the first night, Ne123123 reduced many interest in it.
Now he's in Diablo a maze. The maze is M * N and he's at (0, 0). The destination is (M, N). Every point of the map has an interest value to him.

The maze is so complex that Ne123123 only can move down or right. If he moves down, he only can move one cell on every step. And if he move right, he can moves one step or moves to the column that is the multiple of the number of current column. That is, if he's on (y, x) now, he can moves to (y + 1, x), (y, x + 1) or (y, x * k) (k = 1, 2, 3...)

The first line is an integer T, indicates the number of cases.
Then follow T cases.
Each case contains two integers M, N.
Then follow M lines.
Each line contains N integers Vij, indicates the interest value of every cell.
(1 <= M <= 20, 8 <= N <= 1000. -100 <= Vij <= 100)

For each case, output the maximum interest value.