/*
written by- Piyush Golani
language- c++
country- India
College- N.I.T Jamshedpur
*/
#include <cmath>
#include <ctime>
#include <iostream>
#include <string>
#include <vector>
#include<cstdio>
#include<sstream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<map>
#include<cctype>
#include<queue>
using namespace std;
#define pb push_back
#define all(s) s.begin(),s.end()
#define f(i,a,b) for(int i=a;i<b;i++)
#define F(i,a,b) for(int i=a;i>=b;i--)
#define PI 3.1415926535897932384626433832795
#define INF 1000000005
#define BIG_INF 7000000000000000000LL
#define mp make_pair
#define eps 1e-9
#define LL long long
#define si(n) scanf("%d",&n)
#define sll(n) scanf("%lld",&n)
#define mod 1000000007
#define vv pair<LL,int>
int A[55][55];
int n,m;
LL sumrow[55][55][55],sumcol[55][55][55],Al,Bo;
LL DP[55][55][55][55];
LL Do(int r1,int r2,int c1,int c2)
{
LL &res=DP[r1][r2][c1][c2];
if(res!=-1) return res;
//Alice
if(r1>r2 || c1>c2 || r1>=n || r2<0 || c1<0 || c2>=m) return res=0;
char e;
int y;
int p=INF;
//cout<<r1<<" "<<r2<<" "<<c1<<" "<<c2<<"\n";
if(sumrow[r1][c1][c2]<p)
{
p=sumrow[r1][c1][c2];
e='r';
y=1;
}
if(sumrow[r2][c1][c2]<p)
{
p=sumrow[r2][c1][c2];
e='r';
y=2;
}
if(sumcol[c1][r1][r2]<p)
{
p=sumcol[c1][r1][r2];
e='c';
y=1;
}
if(sumcol[c2][r1][r2]<p)
{
p=sumcol[c2][r1][r2];
e='c';
y=2;
}
//see which one is chosen
if(e=='r')
{
if(y==1)
{
//Al+=sumrow[r1][c1][c2];
r1++;
}
else
{
//Al+=sumrow[r2][c1][c2];
r2--;
}
}
else
{
if(y==1)
{
//Al+=sumcol[c1][r1][r2];
c1++;
}
else
{
//Al+=sumcol[c2][r1][r2];
c2--;
}
}
LL a=0;
if(r1<=r2 && c1<=c2 && c1<m && c2>=0 && r1<n && r2>=0)
{
a=max(max(sumrow[r1][c1][c2]+Do(r1+1,r2,c1,c2),sumrow[r2][c1][c2]+Do(r1,r2-1,c1,c2)),max(sumcol[c1][r1][r2]+Do(r1,r2,c1+1,c2),sumcol[c2][r1][r2]+Do(r1,r2,c1,c2-1)));
}
return res=a;
}
int main()
{
int t;
si(t);
while(t--)
{
si(n); si(m);
LL sum=0;
f(i,0,n)
{
f(j,0,m)
{
si(A[i][j]);
sum+=A[i][j];
}
}
f(i,0,n)
{
f(j,0,m)
{
f(k,0,m)
{
if(j==k)
{
sumrow[i][j][k]=A[i][j];
continue;
}
sumrow[i][j][k]=sumrow[i][j][k-1]+A[i][k];
}
}
}
f(i,0,m)
{
f(j,0,n)
{
f(k,0,n)
{
if(j==k)
{
sumcol[i][j][k]=A[j][i];
continue;
}
sumcol[i][j][k]=sumcol[i][j][k-1]+A[k][i];
}
}
}
//Al=0,Bo=0;
memset(DP,-1,sizeof(DP));
Bo=Do(0,n-1,0,m-1);
Al=sum-Bo;
//cout<<Al<<" "<<Bo<<"\n";
if(Al==Bo) Bo+=Al;
printf("%lld\n",max(Al,Bo));
}
return 0;
}
LyoKd3JpdHRlbiBieS0gUGl5dXNoIEdvbGFuaQpsYW5ndWFnZS0gYysrCmNvdW50cnktIEluZGlhCkNvbGxlZ2UtIE4uSS5UIEphbXNoZWRwdXIKKi8KI2luY2x1ZGUgPGNtYXRoPgojaW5jbHVkZSA8Y3RpbWU+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGU8Y3N0ZGlvPgojaW5jbHVkZTxzc3RyZWFtPgojaW5jbHVkZTxhbGdvcml0aG0+CiNpbmNsdWRlPGNzdGRsaWI+CiNpbmNsdWRlPGNzdHJpbmc+CiNpbmNsdWRlPG1hcD4KI2luY2x1ZGU8Y2N0eXBlPgojaW5jbHVkZTxxdWV1ZT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBhbGwocykgcy5iZWdpbigpLHMuZW5kKCkKI2RlZmluZSBmKGksYSxiKSBmb3IoaW50IGk9YTtpPGI7aSsrKQojZGVmaW5lIEYoaSxhLGIpIGZvcihpbnQgaT1hO2k+PWI7aS0tKQojZGVmaW5lIFBJIDMuMTQxNTkyNjUzNTg5NzkzMjM4NDYyNjQzMzgzMjc5NQojZGVmaW5lIElORiAxMDAwMDAwMDA1CiNkZWZpbmUgQklHX0lORiA3MDAwMDAwMDAwMDAwMDAwMDAwTEwKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBlcHMgMWUtOQojZGVmaW5lIExMIGxvbmcgbG9uZwojZGVmaW5lIHNpKG4pIHNjYW5mKCIlZCIsJm4pCiNkZWZpbmUgc2xsKG4pIHNjYW5mKCIlbGxkIiwmbikKI2RlZmluZSBtb2QgMTAwMDAwMDAwNwojZGVmaW5lIHZ2IHBhaXI8TEwsaW50PgoKaW50IEFbNTVdWzU1XTsKaW50IG4sbTsKTEwgc3Vtcm93WzU1XVs1NV1bNTVdLHN1bWNvbFs1NV1bNTVdWzU1XSxBbCxCbzsKTEwgRFBbNTVdWzU1XVs1NV1bNTVdOwpMTCBEbyhpbnQgcjEsaW50IHIyLGludCBjMSxpbnQgYzIpCnsKICAgIExMICZyZXM9RFBbcjFdW3IyXVtjMV1bYzJdOwogICAgaWYocmVzIT0tMSkgcmV0dXJuIHJlczsKICAgIC8vQWxpY2UKICAgIGlmKHIxPnIyIHx8IGMxPmMyIHx8IHIxPj1uIHx8IHIyPDAgfHwgYzE8MCB8fCBjMj49bSkgcmV0dXJuIHJlcz0wOwogICAgY2hhciBlOwogICAgaW50IHk7CiAgICBpbnQgcD1JTkY7CiAgICAvL2NvdXQ8PHIxPDwiICI8PHIyPDwiICI8PGMxPDwiICI8PGMyPDwiXG4iOwogICAgaWYoc3Vtcm93W3IxXVtjMV1bYzJdPHApCiAgICB7CiAgICAgICAgcD1zdW1yb3dbcjFdW2MxXVtjMl07CiAgICAgICAgZT0ncic7CiAgICAgICAgeT0xOwogICAgfQogICAgaWYoc3Vtcm93W3IyXVtjMV1bYzJdPHApCiAgICB7CiAgICAgICAgcD1zdW1yb3dbcjJdW2MxXVtjMl07CiAgICAgICAgZT0ncic7CiAgICAgICAgeT0yOwogICAgfQogICAgaWYoc3VtY29sW2MxXVtyMV1bcjJdPHApCiAgICB7CiAgICAgICAgcD1zdW1jb2xbYzFdW3IxXVtyMl07CiAgICAgICAgZT0nYyc7CiAgICAgICAgeT0xOwogICAgfQogICAgaWYoc3VtY29sW2MyXVtyMV1bcjJdPHApCiAgICB7CiAgICAgICAgcD1zdW1jb2xbYzJdW3IxXVtyMl07CiAgICAgICAgZT0nYyc7CiAgICAgICAgeT0yOwogICAgfQogICAgLy9zZWUgd2hpY2ggb25lIGlzIGNob3NlbgogICAgaWYoZT09J3InKQogICAgewogICAgICAgIGlmKHk9PTEpCiAgICAgICAgewogICAgICAgICAgICAvL0FsKz1zdW1yb3dbcjFdW2MxXVtjMl07CiAgICAgICAgICAgIHIxKys7CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIC8vQWwrPXN1bXJvd1tyMl1bYzFdW2MyXTsKICAgICAgICAgICAgcjItLTsKICAgICAgICB9CiAgICB9CiAgICBlbHNlCiAgICB7CiAgICAgICAgaWYoeT09MSkKICAgICAgICB7CiAgICAgICAgICAgIC8vQWwrPXN1bWNvbFtjMV1bcjFdW3IyXTsKICAgICAgICAgICAgYzErKzsKICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgLy9BbCs9c3VtY29sW2MyXVtyMV1bcjJdOwogICAgICAgICAgICBjMi0tOwogICAgICAgIH0KICAgIH0KICAgIExMIGE9MDsKICAgIGlmKHIxPD1yMiAmJiBjMTw9YzIgJiYgYzE8bSAmJiBjMj49MCAmJiByMTxuICYmIHIyPj0wKQogICAgewogICAgICAgIGE9bWF4KG1heChzdW1yb3dbcjFdW2MxXVtjMl0rRG8ocjErMSxyMixjMSxjMiksc3Vtcm93W3IyXVtjMV1bYzJdK0RvKHIxLHIyLTEsYzEsYzIpKSxtYXgoc3VtY29sW2MxXVtyMV1bcjJdK0RvKHIxLHIyLGMxKzEsYzIpLHN1bWNvbFtjMl1bcjFdW3IyXStEbyhyMSxyMixjMSxjMi0xKSkpOwoKICAgIH0KCiAgICByZXR1cm4gcmVzPWE7Cn0KCmludCBtYWluKCkKewogICAgaW50IHQ7CiAgICBzaSh0KTsKICAgIHdoaWxlKHQtLSkKICAgIHsKICAgICAgICBzaShuKTsgc2kobSk7CiAgICAgICAgTEwgc3VtPTA7CiAgICAgICAgZihpLDAsbikKICAgICAgICB7CiAgICAgICAgICAgIGYoaiwwLG0pCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHNpKEFbaV1bal0pOwogICAgICAgICAgICAgICAgc3VtKz1BW2ldW2pdOwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICBmKGksMCxuKQogICAgICAgIHsKICAgICAgICAgICAgZihqLDAsbSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgZihrLDAsbSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBpZihqPT1rKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgc3Vtcm93W2ldW2pdW2tdPUFbaV1bal07CiAgICAgICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICBzdW1yb3dbaV1bal1ba109c3Vtcm93W2ldW2pdW2stMV0rQVtpXVtrXTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBmKGksMCxtKQogICAgICAgIHsKICAgICAgICAgICAgZihqLDAsbikKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgZihrLDAsbikKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBpZihqPT1rKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgc3VtY29sW2ldW2pdW2tdPUFbal1baV07CiAgICAgICAgICAgICAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgICAgICBzdW1jb2xbaV1bal1ba109c3VtY29sW2ldW2pdW2stMV0rQVtrXVtpXTsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICAvL0FsPTAsQm89MDsKICAgICAgICBtZW1zZXQoRFAsLTEsc2l6ZW9mKERQKSk7CiAgICAgICAgQm89RG8oMCxuLTEsMCxtLTEpOwogICAgICAgIEFsPXN1bS1CbzsKICAgICAgICAvL2NvdXQ8PEFsPDwiICI8PEJvPDwiXG4iOwogICAgICAgIGlmKEFsPT1CbykgQm8rPUFsOwogICAgICAgIHByaW50ZigiJWxsZFxuIixtYXgoQWwsQm8pKTsKICAgIH0KICAgIHJldHVybiAwOwp9Cg==