#include <stdio.h>
#include <algorithm>
int p[501][501], dp[501][501], zero[501][501];
//zero[i][j] will store whether any value is <=0 in the path from (0,0) to (i,j)
int max(int a, int b)
{
return (a > b ? a : b);
}
int main()
{
int times;
scanf("%d", ×);
while (times--)
{
int r, c, i, j;
scanf("%d %d", &r, &c);
for (i = 0; i < r; i++)
{
for (j = 0; j < c; j++)
{
scanf("%d", &p[i][j]);
}
}
int mid,lo=1,hi=(r+c)*1000+6,min=1048577;
while(lo<=hi)
{
mid=(lo+hi)>>1;
for (i = 0; i < r; i++)
{
for (j = 0; j < c; j++)
{
dp[i][j]=p[i][j];
zero[i][j]=0;
}
}
dp[0][0]=mid;
// top row
for (j = 1; j < c ; j++)
{
dp[0][j] += dp[0][j-1];
if(dp[0][j]<=0 || zero[0][j-1]==1)
{
zero[0][j]=1;
}
}
// first column
for (i = 1; i < r ; i++)
{
dp[i][0] += dp[i-1][0];
if(dp[i][0]<=0 || zero[i-1][0]==1)
{
zero[i][0]=1;
}
}
// non boundary elements
for (i = 1; i < r ; i++)
{
for (j = 1; j < c ; j++)
{
if(dp[i-1][j] == dp[i][j-1])
{
dp[i][j] += dp[i-1][j];
zero[i][j] = std::min(zero[i-1][j],zero[i][j-1]);
}
else if(zero[i-1][j] > zero[i][j-1] || ((zero[i-1][j] == zero[i][j-1]) && (dp[i-1][j] < dp[i][j-1])))
{
dp[i][j] += dp[i][j-1];
zero[i][j] = zero[i][j-1];
}else
{
dp[i][j] += dp[i-1][j];
zero[i][j] = zero[i-1][j];
}
if(dp[i][j]<=0)zero[i][j]=1;
}
}
if(zero[r-1][c-1]==0 && min > mid) min=mid;
if(zero[r-1][c-1]==0)hi=mid-1;
else lo=mid+1;
}
printf("%d\n", min);
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxhbGdvcml0aG0+CmludCBwWzUwMV1bNTAxXSwgZHBbNTAxXVs1MDFdLCB6ZXJvWzUwMV1bNTAxXTsgCi8vemVyb1tpXVtqXSB3aWxsIHN0b3JlIHdoZXRoZXIgYW55IHZhbHVlIGlzIDw9MCBpbiB0aGUgcGF0aCBmcm9tICgwLDApIHRvIChpLGopIAppbnQgbWF4KGludCBhLCBpbnQgYikKewogIHJldHVybiAoYSA+IGIgPyBhIDogYik7ICAgCn0KaW50IG1haW4oKQp7CiAgICBpbnQgdGltZXM7CiAgICBzY2FuZigiJWQiLCAmdGltZXMpOwogICAgCiAgICB3aGlsZSAodGltZXMtLSkKICAgIHsKICAgICAgICAgIGludCByLCBjLCBpLCBqOwogICAgICAgICAgc2NhbmYoIiVkICVkIiwgJnIsICZjKTsKICAgICAgICAgIGZvciAoaSA9IDA7IGkgPCByOyBpKyspCiAgICAgICAgICB7CiAgICAgICAgICAgICAgZm9yIChqID0gMDsgaiA8IGM7IGorKykKICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgIHNjYW5mKCIlZCIsICZwW2ldW2pdKTsKICAgICAgICAgICAgICB9CiAgICAgICAgICB9CiAgICAgICAgICBpbnQgbWlkLGxvPTEsaGk9KHIrYykqMTAwMCs2LG1pbj0xMDQ4NTc3OwogICAgICAgICAgd2hpbGUobG88PWhpKQogICAgICAgICAgewogICAgICAgICAgCSAgbWlkPShsbytoaSk+PjE7CiAgICAgICAgICAJICBmb3IgKGkgPSAwOyBpIDwgcjsgaSsrKQoJCSAgICAgIHsKCQkgICAgICAgICAgZm9yIChqID0gMDsgaiA8IGM7IGorKykKCQkgICAgICAgICAgewoJCSAgICAgICAgICAJZHBbaV1bal09cFtpXVtqXTsKCQkgICAgICAgICAgCXplcm9baV1bal09MDsJCgkJICAgICAgICAgIH0KCQkgICAgICB9CgkJICAgICAgZHBbMF1bMF09bWlkOwoJICAgICAgICAgIC8vIHRvcCByb3cKCSAgICAgICAgICBmb3IgKGogPSAxOyBqIDwgYyA7IGorKykKICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgCSAgZHBbMF1bal0gKz0gZHBbMF1bai0xXTsgCgkJCQkgIGlmKGRwWzBdW2pdPD0wIHx8IHplcm9bMF1bai0xXT09MSkKCQkJCSAgewoJCQkJICAJemVyb1swXVtqXT0xOwoJCQkJICB9CQogICAgICAgICAgICAgIH0KCSAgICAgICAgICAvLyBmaXJzdCBjb2x1bW4KCSAgICAgICAgICBmb3IgKGkgPSAxOyBpIDwgciA7IGkrKykKICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgCSAgZHBbaV1bMF0gKz0gZHBbaS0xXVswXTsJCiAgICAgICAgICAgICAgCSAgaWYoZHBbaV1bMF08PTAgfHwgemVyb1tpLTFdWzBdPT0xKQoJCQkJICB7CgkJCQkgIAl6ZXJvW2ldWzBdPTE7CgkJCQkgIH0JCiAgICAgICAgICAgICAgfQoJICAgICAgICAgIAoJICAgICAgICAgIC8vIG5vbiBib3VuZGFyeSBlbGVtZW50cwoJICAgICAgICAgIGZvciAoaSA9IDE7IGkgPCByIDsgaSsrKQoJICAgICAgICAgIHsKCSAgICAgICAgICAgICAgZm9yIChqID0gMTsgaiA8IGMgOyBqKyspCgkgICAgICAgICAgICAgIHsKCSAgICAgICAgICAgICAgCSAgaWYoZHBbaS0xXVtqXSA9PSBkcFtpXVtqLTFdKQoJICAgICAgICAgICAgICAJICB7CgkgICAgICAgICAgICAgIAkgIAkJZHBbaV1bal0gKz0gZHBbaS0xXVtqXTsKCSAgICAgICAgICAgICAgICAgIAkJemVyb1tpXVtqXSA9IHN0ZDo6bWluKHplcm9baS0xXVtqXSx6ZXJvW2ldW2otMV0pOwkKCSAgICAgICAgICAgICAgCSAgfQoJICAgICAgICAgICAgICAJICBlbHNlIGlmKHplcm9baS0xXVtqXSA+IHplcm9baV1bai0xXSB8fCAoKHplcm9baS0xXVtqXSA9PSB6ZXJvW2ldW2otMV0pICYmIChkcFtpLTFdW2pdIDwgZHBbaV1bai0xXSkpKQoJICAgICAgICAgICAgICAJICB7CgkgICAgICAgICAgICAgIAkgIAkJZHBbaV1bal0gKz0gZHBbaV1bai0xXTsKCSAgICAgICAgICAgICAgCSAgCQl6ZXJvW2ldW2pdID0gemVyb1tpXVtqLTFdOwoJICAgICAgICAgICAgICAJICB9ZWxzZQoJICAgICAgICAgICAgICAJICB7CgkgICAgICAgICAgICAgIAkgIAkJZHBbaV1bal0gKz0gZHBbaS0xXVtqXTsKCSAgICAgICAgICAgICAgICAgIAkJemVyb1tpXVtqXSA9IHplcm9baS0xXVtqXTsKCQkJCQkgIH0KCSAgICAgICAgICAgICAgCSAgaWYoZHBbaV1bal08PTApemVyb1tpXVtqXT0xOwoJICAgICAgICAgICAgICB9CgkgICAgICAgICAgfQoJICAgICAgICAgCgkgICAgICAgICBpZih6ZXJvW3ItMV1bYy0xXT09MCAmJiBtaW4gPiBtaWQpIG1pbj1taWQ7CgkgICAgICAgICBpZih6ZXJvW3ItMV1bYy0xXT09MCloaT1taWQtMTsKCSAgICAgICAgIGVsc2UgbG89bWlkKzE7CiAgICAgICAgICB9CiAgICAgIAkgIHByaW50ZigiJWRcbiIsIG1pbik7CiAgICB9CiAgICByZXR1cm4gMDsKfQ==