#include <cstdio>#include <cstdlib>#include <cstring>#include <cmath>#include <algorithm>using namespace std;#define inf (0x3f3f3f3f)typedef long long int LL;#include <iostream>#include <sstream>#include <vector>#include <set>#include <map>#include <queue>#include <string>const int maxn=500+20;LL dp[maxn][maxn];int n,m;int a[maxn][maxn];bool check (LL val){    dp[1][1]=val;    for (int i=1;i<=n;++i)    {        for (int j=1;j<=m;++j)        {            if (i==1 && j==1)continue;            if (dp[i-1][j]<=0) dp[i-1][j]=-inf; //如果小于0，证明已经不能走了            if (dp[i][j-1]<=0) dp[i][j-1]=-inf;            if (dp[i-1][j]<=0 && dp[i][j-1]<=0) dp[i][j]=-inf;            else dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];        }    }    return dp[n][m]>0;}void work (){    scanf("%d%d",&n,&m);    for (int i=1;i<=n;++i)        for (int j=1;j<=m;++j)            scanf("%d",&a[i][j]);    LL begin=1,end=1LL*500*500*1000+20;    while (begin<=end)    {        LL mid = (begin+end)>>1;        //printf ("%d\n",mid);        if (check(mid))            end=mid-1;        else begin=mid+1;    }    printf ("%lld\n",begin);    //check(998);    //check(3);     //printf ("%d\n",check(1002));//    printf ("%lld\n",dp[2][4]);    return ;}int main(){#ifdef local    freopen("data.txt","r",stdin);#endif    for (int i=1;i<=500;++i)    {        dp[0][i]=-inf;        dp[i][0]=-inf;    }    dp[0][0]=-inf;    dp[0][1]=0;    dp[1][0]=0;    int t;    scanf("%d",&t);    while (t--) work();    return 0;}