#include#include #include using namespace std; char mp[410][410]; int b[410][410],w[410][410]; int u[410],d[410]; int n,m; int calw(int x1,int y1,int x2,int y2){ return w[x2][y2]-w[x1-1][y2]-w[x2][y1-1]+w[x1-1][y1-1]; } int calb(int x1,int y1,int x2,int y2){ return b[x2][y2]-b[x1-1][y2]-b[x2][y1-1]+b[x1-1][y1-1]; } int cal(int l,int r) { int ans=1e9; u[0]=d[0]=0; d[++d[0]]=n; for(int i=n-1;i;i--) { int hd =(d[d[0]]-i)-calb(i,l,d[d[0]]-1,l); hd+=(d[d[0]]-i)-calb(i,r,d[d[0]]-1,r); hd+=(r-l-1)-calb(d[d[0]],l+1,d[d[0]],r-1); hd+=(r-l-1)*(d[d[0]]-i)-calw(i,l+1,d[d[0]]-1,r-1); int hn =r-l-1-calb(i,l+1,i,r-1); if(hd>hn) d[++d[0]]=i; } u[++u[0]]=1; for(int i=2;i<=n;i++) { int hu =(i-u[u[0]])-calb(u[u[0]]+1,l,i,l); hu+=(i-u[u[0]])-calb(u[u[0]]+1,r,i,r); hu+=(r-l-1)-calb(u[u[0]],l+1,u[u[0]],r-1); hu+=(r-l-1)*(i-u[u[0]])-calw(u[u[0]]+1,l+1,i,r-1); int hn =r-l-1-calb(i,l+1,i,r-1); if(hu>hn) u[++u[0]]=i; } reverse(d+1,d+d[0]+1); int p=1; for(int i=1;i<=u[0];i++) { while(p<=d[0]&&d[p]-u[i]<4) p++; if(p>d[0]) break; int hf =(r-l-1)*(d[p]-u[i]-1)-calw(u[i]+1,l+1,d[p]-1,r-1); hf+=(r-l-1)-calb(u[i],l+1,u[i],r-1); hf+=(r-l-1)-calb(d[p],l+1,d[p],r-1); hf+=(d[p]-u[i]-1)-calb(u[i]+1,l,d[p]-1,l); hf+=(d[p]-u[i]-1)-calb(u[i]+1,r,d[p]-1,r); ans=min(ans,hf); } return ans; } int main() { int t; cin>>t; while(t--) { int ans=1e9; cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { char c=getchar(); while(c==' '||c=='n') c=getchar(); mp[i][j]=c; b[i][j]=b[i][j-1]+b[i-1][j]-b[i-1][j-1]+(mp[i][j]=='1'); w[i][j]=w[i][j-1]+w[i-1][j]-w[i-1][j-1]+(mp[i][j]=='0'); } for(int i=1;i<=m;i++) for(int j=i+3;j<=m;j++) ans=min(ans,cal(i,j)); cout<



