D :: The Most Valuable Queen

Time Limit: 4 Seconds    Memory Limit: 32768 KB

Each square of an n×m  chessboard is associated with a value which is a positive integer number. For a queen on the chessboard, its value is defined to be the sum of the values of all squares threatened by the queen including the square in which queen stands. Your job is to find the most valuable queen (a queen whose value is maximum).

Input

The first line of the input includes the number of test cases, 1≤t≤100. First line of each test case contains two integers, 1≤n≤1000, the number of the chessboard rows and 1≤m≤1000, the number of the chessboard columns. Each of the following n lines contains m integers separated with spaces. The j-th number in the i-the line is the value of the square placed in i-th row and j-th column of the chessboard. All value are positive and less than 1000.

Output

For each test case, print the value of the most valuable queen in one line.

Sample Input

2
4 3 
1 2 3 
4 5 6
7 8 9
1 2 3
4 4
1 2 1 2
2 1 2 1
1 2 1 2
2 1 2 1

Sample Output

47
20

Submit

Source: 12th Iran Nationwide Internet Contest I