#include <cstring>
#include <iostream>
using namespace std;
#define SIZE 51
#define ULL long long
int minIndex(int size, ULL arr[])
{
int i=0,index = 0;
ULL min=arr[0];
for(i=1;i<size;++i)
{
if(arr[i] < min)
{
min = arr[i];
index = i;
}
}
return index;
}
int maxIndex(int size, ULL arr[])
{
int i=0,index = 0;
ULL min=arr[0];
for(i=1;i<size;++i)
{
if(arr[i] > min)
{
min = arr[i];
index = i;
}
}
return index;
}
ULL final;
void backtrack(ULL mat[SIZE][SIZE],
ULL sumR[SIZE][SIZE], ULL sumC[SIZE][SIZE],
int sr, int sc, int er, int ec, ULL alice, ULL bob)
{
ULL check[4];
ULL all;
if(sr < 1 || sc < 1 || (sr > er) || (sc > ec))
{
if(alice == bob)
{
all = alice+bob;
if(all > final)
final = all;
}
else
{
if(bob > final)
final = bob;
}
return ;
}
// for bob we know the pririty.
check[0] = sumR[sr][ec] - sumR[sr][sc-1];
check[1] = sumR[er][ec] - sumR[er][sc-1];
check[2] = sumC[er][sc] - sumC[sr-1][sc];
check[3] = sumC[er][ec] - sumC[sr-1][ec];
int ret = minIndex(4,check);
switch(ret)
{
case 0: ++sr; break;
case 1:--er;break;
case 2:++sc;break;
case 3:--ec;
}
alice += check[ret];
//if((sr > er) || (sc > ec))
{
if(alice == bob)
{
all = alice+bob;
if(all > final)
final = all;
}
else
{
if(bob > final)
final = bob;
}
}
// it was done for bob
check[0] = sumR[sr][ec] - sumR[sr][sc-1];
check[1] = sumR[er][ec] - sumR[er][sc-1];
check[2] = sumC[er][sc] - sumC[sr-1][sc];
check[3] = sumC[er][ec] - sumC[sr-1][ec];
ret = maxIndex(4,check);
ULL max = check[ret];
int in=0;
for(in=ret;in<4;++in)
{
if(max == check[in])
{
// got minimum for this backtrack for next
// after changing the parameters sr, er, sc, ec
switch(in)
{
case 0: ++sr;break;
case 1:--er;break;
case 2:++sc;break;
case 3:--ec;
}
//bob += check[ret];
backtrack(mat, sumR, sumC, sr, sc, er, ec, alice, bob+max);
//bob -= check[ret];
switch(in)
{
case 0: --sr;break;
case 1:++er;break;
case 2:--sc;break;
case 3:++ec;
}
}
}
//if((sr > er) || (sc > ec))
{
if(alice == bob)
{
all = alice+bob;
if(all > final)
final = all;
}
else
{
if(bob > final)
final = bob;
}
}
}
int main()
{
int t,n,m,i,j,sr,er,sc,ec,ret,taken;
ULL mat[SIZE][SIZE], row[SIZE], col[SIZE], sumR[SIZE][SIZE], sumC[SIZE][SIZE];
ULL win,bob,alice,firstr,lastr,firstc,lastc;
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&m);
//memset(row,0,sizeof(ULL)*SIZE);
//memset(col,0,sizeof(ULL)*SIZE);
win = bob = alice = firstr = lastr = firstc = lastc = 0;
sr = er = sc = ec = ret = taken = 0;
for(i=0;i<=n;++i)
{
// TODO: required only 1 time
memset(sumR[i],0,sizeof(ULL)*SIZE);
}
for(i=0;i<=m;++i)
{
memset(sumC[i],0,sizeof(ULL)*SIZE);
}
for(i=1;i<=n;++i)
{
for(j=1;j<=m;++j)
{
scanf("%lld", &mat[i][j]);
sumR[i][j] += sumR[i][j-1] + mat[i][j];
sumC[i][j] += sumC[i-1][j] + mat[i][j];
}
}
final = 0;
backtrack(mat, sumR, sumC, 1, 1, n, m, 0, 0);
printf("%lld\n", final);
}
}
I2luY2x1ZGUgPGNzdHJpbmc+CiNpbmNsdWRlIDxpb3N0cmVhbT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBTSVpFIDUxCiNkZWZpbmUgVUxMIGxvbmcgbG9uZwoKaW50IG1pbkluZGV4KGludCBzaXplLCBVTEwgYXJyW10pCnsKICAgIGludCBpPTAsaW5kZXggPSAwOwoJVUxMIG1pbj1hcnJbMF07Cglmb3IoaT0xO2k8c2l6ZTsrK2kpCgl7CgkJaWYoYXJyW2ldIDwgbWluKQoJCXsKCQkJbWluID0gYXJyW2ldOwoJCQlpbmRleCA9IGk7CgkJfQoJfQoJcmV0dXJuIGluZGV4Owp9CgppbnQgbWF4SW5kZXgoaW50IHNpemUsIFVMTCBhcnJbXSkKewoJaW50IGk9MCxpbmRleCA9IDA7CglVTEwgbWluPWFyclswXTsKCWZvcihpPTE7aTxzaXplOysraSkKCXsKCQlpZihhcnJbaV0gPiBtaW4pCgkJewoJCQltaW4gPSBhcnJbaV07CgkJCWluZGV4ID0gaTsKCQl9Cgl9CglyZXR1cm4gaW5kZXg7Cn0KClVMTCBmaW5hbDsKdm9pZCBiYWNrdHJhY2soVUxMIG1hdFtTSVpFXVtTSVpFXSwgCglVTEwgc3VtUltTSVpFXVtTSVpFXSwgVUxMIHN1bUNbU0laRV1bU0laRV0sCglpbnQgc3IsIGludCBzYywgaW50IGVyLCBpbnQgZWMsIFVMTCBhbGljZSwgVUxMIGJvYikgCgl7CgkJVUxMIGNoZWNrWzRdOwoJCVVMTCBhbGw7CgkJCgkJaWYoc3IgPCAxIHx8IHNjIDwgMSB8fCAoc3IgPiBlcikgfHwgKHNjID4gZWMpKQoJCXsKCQkJaWYoYWxpY2UgPT0gYm9iKQoJCQl7CgkJCQlhbGwgPSBhbGljZStib2I7CgkJCQlpZihhbGwgPiBmaW5hbCkKCQkJCQlmaW5hbCA9IGFsbDsKCQkJfQoJCQllbHNlCgkJCXsKCQkJCWlmKGJvYiA+IGZpbmFsKQoJCQkJCWZpbmFsID0gYm9iOwoJCQl9CgkJCXJldHVybiA7CgkJfQoJCS8vIGZvciBib2Igd2Uga25vdyB0aGUgcHJpcml0eS4KCQljaGVja1swXSA9IHN1bVJbc3JdW2VjXSAtIHN1bVJbc3JdW3NjLTFdOyAKICAgIAljaGVja1sxXSA9IHN1bVJbZXJdW2VjXSAtIHN1bVJbZXJdW3NjLTFdOwogICAgCWNoZWNrWzJdID0gc3VtQ1tlcl1bc2NdIC0gc3VtQ1tzci0xXVtzY107CiAgICAJY2hlY2tbM10gPSBzdW1DW2VyXVtlY10gLSBzdW1DW3NyLTFdW2VjXTsKICAgICAJaW50IHJldCA9IG1pbkluZGV4KDQsY2hlY2spOwogICAgIAkKICAgICAJc3dpdGNoKHJldCkKCSAgICB7CgkJCWNhc2UgMDogKytzcjsgYnJlYWs7CgkJICAgIGNhc2UgMTotLWVyO2JyZWFrOwoJCSAgICBjYXNlIDI6KytzYzticmVhazsKCQkgICAgY2FzZSAzOi0tZWM7CgkJfQoJCQoJCWFsaWNlICs9IGNoZWNrW3JldF07CgkJCgkJCgkJLy9pZigoc3IgPiBlcikgfHwgKHNjID4gZWMpKQoJCXsKCQkJaWYoYWxpY2UgPT0gYm9iKQoJCQl7CgkJCQlhbGwgPSBhbGljZStib2I7CgkJCQlpZihhbGwgPiBmaW5hbCkKCQkJCQlmaW5hbCA9IGFsbDsKCQkJfQoJCQllbHNlCgkJCXsKCQkJCWlmKGJvYiA+IGZpbmFsKQoJCQkJCWZpbmFsID0gYm9iOwoJCQl9CgkJfQoJCQoJCS8vIGl0IHdhcyBkb25lIGZvciBib2IgCgkJY2hlY2tbMF0gPSBzdW1SW3NyXVtlY10gLSBzdW1SW3NyXVtzYy0xXTsgCiAgICAJY2hlY2tbMV0gPSBzdW1SW2VyXVtlY10gLSBzdW1SW2VyXVtzYy0xXTsKICAgIAljaGVja1syXSA9IHN1bUNbZXJdW3NjXSAtIHN1bUNbc3ItMV1bc2NdOwogICAgCWNoZWNrWzNdID0gc3VtQ1tlcl1bZWNdIC0gc3VtQ1tzci0xXVtlY107CiAgICAgCQogICAgIAlyZXQgPSBtYXhJbmRleCg0LGNoZWNrKTsKICAgICAJVUxMIG1heCA9IGNoZWNrW3JldF07CiAgICAgCWludCBpbj0wOwogICAgIAlmb3IoaW49cmV0O2luPDQ7KytpbikKICAgICAJewoJCQlpZihtYXggPT0gY2hlY2tbaW5dKQoJCQl7CgkJCQkvLyBnb3QgbWluaW11bSBmb3IgdGhpcyBiYWNrdHJhY2sgZm9yIG5leHQKCQkJCS8vIGFmdGVyIGNoYW5naW5nIHRoZSBwYXJhbWV0ZXJzIHNyLCBlciwgc2MsIGVjCgkJCQlzd2l0Y2goaW4pCgkJCSAgICB7CgkJCQkJY2FzZSAwOiArK3NyO2JyZWFrOwoJCQkJICAgIGNhc2UgMTotLWVyO2JyZWFrOwoJCQkJICAgIGNhc2UgMjorK3NjO2JyZWFrOwoJCQkJICAgIGNhc2UgMzotLWVjOwoJCQkJfQoJCQkJLy9ib2IgKz0gY2hlY2tbcmV0XTsKCQkJCWJhY2t0cmFjayhtYXQsIHN1bVIsIHN1bUMsIHNyLCBzYywgZXIsIGVjLCBhbGljZSwgYm9iK21heCk7CgkJCQkvL2JvYiAtPSBjaGVja1tyZXRdOwoJCQkJc3dpdGNoKGluKQoJCQkgICAgewoJCQkJCWNhc2UgMDogLS1zcjticmVhazsKCQkJCSAgICBjYXNlIDE6KytlcjticmVhazsKCQkJCSAgICBjYXNlIDI6LS1zYzticmVhazsKCQkJCSAgICBjYXNlIDM6KytlYzsKCQkJCX0KCQkJfQoJCX0KCQkKCQkvL2lmKChzciA+IGVyKSB8fCAoc2MgPiBlYykpCgkJewoJCQlpZihhbGljZSA9PSBib2IpCgkJCXsKCQkJCWFsbCA9IGFsaWNlK2JvYjsKCQkJCWlmKGFsbCA+IGZpbmFsKQoJCQkJCWZpbmFsID0gYWxsOwoJCQl9CgkJCWVsc2UKCQkJewoJCQkJaWYoYm9iID4gZmluYWwpCgkJCQkJZmluYWwgPSBib2I7CgkJCX0KCQl9CQkKCX0KCmludCBtYWluKCkKewogICAgaW50IHQsbixtLGksaixzcixlcixzYyxlYyxyZXQsdGFrZW47CiAgICAgCiAgICBVTEwgbWF0W1NJWkVdW1NJWkVdLCByb3dbU0laRV0sIGNvbFtTSVpFXSwgc3VtUltTSVpFXVtTSVpFXSwgc3VtQ1tTSVpFXVtTSVpFXTsKICAgICAKICAgIFVMTCB3aW4sYm9iLGFsaWNlLGZpcnN0cixsYXN0cixmaXJzdGMsbGFzdGM7CiAgICAgCiAgICBzY2FuZigiJWQiLCZ0KTsKICAgICAKICAgICAKICAgIHdoaWxlKHQtLSkKICAgICAKICAgIHsKICAgICAKCSAgICBzY2FuZigiJWQgJWQiLCZuLCZtKTsKCSAgICAgCgkgICAgLy9tZW1zZXQocm93LDAsc2l6ZW9mKFVMTCkqU0laRSk7CgkgICAgIAoJICAgIC8vbWVtc2V0KGNvbCwwLHNpemVvZihVTEwpKlNJWkUpOwoJICAgICAKCSAgICB3aW4gPSBib2IgPSBhbGljZSA9IGZpcnN0ciA9IGxhc3RyID0gZmlyc3RjID0gbGFzdGMgPSAwOwoJICAgIHNyID0gZXIgPSBzYyA9IGVjID0gcmV0ID0gdGFrZW4gPSAwOwoJICAgIGZvcihpPTA7aTw9bjsrK2kpCgkgICAgewoJICAgIC8vIFRPRE86IHJlcXVpcmVkIG9ubHkgMSB0aW1lCgkgICAgIG1lbXNldChzdW1SW2ldLDAsc2l6ZW9mKFVMTCkqU0laRSk7CgkgICAgfQoJICAgIAoJICAgIGZvcihpPTA7aTw9bTsrK2kpCQoJICAgIHsKCSAgICAgbWVtc2V0KHN1bUNbaV0sMCxzaXplb2YoVUxMKSpTSVpFKTsKCSAgICB9CgkgICAgZm9yKGk9MTtpPD1uOysraSkKCSAgICB7CgkJICAgIGZvcihqPTE7ajw9bTsrK2opCgkJICAgIHsKCQkJICAgIHNjYW5mKCIlbGxkIiwgJm1hdFtpXVtqXSk7CgkJCSAgICBzdW1SW2ldW2pdICs9IHN1bVJbaV1bai0xXSArIG1hdFtpXVtqXTsgICAgIAoJCQkgICAgc3VtQ1tpXVtqXSArPSBzdW1DW2ktMV1bal0gKyBtYXRbaV1bal07CgkJICAgIH0KCSAgICB9CgkgICAgCgkgICAgZmluYWwgPSAwOwoJICAgIGJhY2t0cmFjayhtYXQsIHN1bVIsIHN1bUMsIDEsIDEsIG4sIG0sIDAsIDApOwoJICAgIHByaW50ZigiJWxsZFxuIiwgZmluYWwpOwoJfQp9