#include<bits/stdc++.h> #define ll long long using namespace std; const int N=310; ll f[N][N][2],f1[N][N],f2[N][N]; int n,m; int a[N][N]; void slv(){ cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++) cin>>a[i][j]; } for(int i=0;i<=n+1;i++){ for(int j=0;j<=m+1;j++) f[i][j][0]=1e18,f[i][j][1]=1e18, f1[i][j]=0,f2[i][j]=0; } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ f1[i][j]=max(f1[i-1][j],f1[i][j-1])+a[i][j]; } }for(int i=n;i>=1;i--){ for(int j=m;j>=1;j--){ f2[i][j]=max(f2[i+1][j],f2[i][j+1])+a[i][j]; } } f[n][1][0]=0,f[n][1][1]=0; //0 up 1 right for(int i=n;i>=1;i--){ for(int j=1;j<=m;j++){ ll mx=max(f1[i][j-1],f1[i-1][j]),val=0; for(int k=j+1;k<=m;k++){ val=max(val,f2[i+1][k]+mx); f[i][k][1]=min(f[i][k][1],max(f[i][j][0],max(val,mx+f2[i][k+1]))); val=max(val,f1[i-1][k]+f2[i+1][k]); mx=max(mx,f1[i-1][k]); }mx=max(f2[i+1][j],f2[i][j+1]),val=0; for(int k=i-1;k>=1;k--){ val=max(val,f1[k][j-1]+mx); f[k][j][0]=min(f[k][j][0],max(f[i][j][1],max(val,mx+f1[k-1][j]))); val=max(val,f1[k][j-1]+f2[k][j+1]); mx=max(mx,f2[k][j+1]); } } }cout<<min(f[1][m][0],f[1][m][1])<<endl; } int main(){ int t;cin>>t; while(t--) slv(); return 0; }