#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m; ll a[305][305],f1[305][305][305],f2[305][305][305],dp[305][305][2],F[305][305],G[305][305],tmp[305][305]; void slv(){ n=read(),m=read(); up(i,1,n)up(j,1,m)a[i][j]=read(); up(i,1,n)up(j,1,m)F[i][j]=max(F[i-1][j],F[i][j-1])+a[i][j]; up(i,1,n+1)up(j,1,m+1)G[i][j]=0; down(i,n,1)down(j,m,1)G[i][j]=max(G[i+1][j],G[i][j+1])+a[i][j]; up(i,1,n)up(j,1,m)f1[i][j][j]=F[i-1][j]+G[i+1][j]; up(i,1,n)up(len,2,m)up(j,1,m-len+1){int l=j,r=j+len-1;f1[i][l][r]=max(f1[i][l][r-1],f1[i][l+1][r]);} up(i,1,n){up(j,1,m)up(k,j,m)tmp[j][k]=f1[i][j][k];up(j,1,m)up(k,j,m)f1[i][j][k]=tmp[j+1][k-1];} up(i,1,n)up(j,1,m)down(k,j-1,1)f1[i][k][j]=max({f1[i][k+1][j],f1[i][k][j],F[i-1][k]+G[i][j+1]}); up(i,1,m)up(j,1,n)f2[i][j][j]=F[j][i-1]+G[j][i+1]; up(i,1,m)up(len,2,n)up(j,1,n-len+1){int l=j,r=j+len-1;f2[i][l][r]=max(f2[i][l][r-1],f2[i][l+1][r]);} up(i,1,m){up(j,1,n)up(k,j,n)tmp[j][k]=f2[i][j][k];up(j,1,n)up(k,j,n)f2[i][j][k]=tmp[j+1][k-1];} up(i,1,m)up(j,1,n)down(k,j-1,1)f2[i][k][j]=max({f2[i][k+1][j],f2[i][k][j],F[k][i-1]+G[j+1][i]}); up(i,1,n)up(j,1,m)up(o,0,1)dp[i][j][o]=1e18; dp[1][m][0]=dp[1][m][1]=0; up(i,1,n)down(j,m,1){ up(k,1,j-1)dp[i][k][1]=min(dp[i][k][1],max({dp[i][j][0],f1[i][k][j],max(F[i][k-1],F[i-1][k])+max(G[i+1][k+1],G[i][j+1])})); up(k,i+1,n)dp[k][j][0]=min(dp[k][j][0],max({dp[i][j][1],f2[j][i][k],max(F[i-1][j],F[i][j-1])+max(G[i+1][j+1],G[k+1][j])})); } printf("%lld\n",min(dp[n][1][0],dp[n][1][1])); } int main(){ //freopen("game.in","r",stdin),freopen("game.out","w",stdout); int t=read();while(t--)slv(); return 0; }