#include <bits/stdc++.h>
using namespace std;
char a[1000010],b[1000010];
int n,m,x[1000010],y[1000010],l[1000010],r[1000010],X,Y,L,R,fx[4][2]={{0,1},{0,-1},{1,0},{-1,0}},lst[1000010];
bool vis[1000010];
struct seg{
	int l,r;
};
struct bit{
	int tr[1000010];
	void clr(){
		for(int i=1;i<=m;i++) tr[i]=0;
	}
	void add(int x,int c){
		for(int i=x;i<=m;i+=(i&-i)) tr[i]+=c;
	}
	int qry(int x){
		int res=0;
		for(int i=x;i;i-=(i&-i)) res+=tr[i];
		return res;
	}
}Lt,Rt;
vector<seg>ad[1000010],dl[1000010];
void dfs(int i,int j){
	X=min(i,X),Y=max(i,Y),L=min(j,L),R=max(j,R);
	vis[(i-1)*m+j]=1;
	for(int k=0;k<4;k++){
		int xx=i+fx[k][0],yy=j+fx[k][1];
		if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&a[(xx-1)*m+yy]=='0'&&!vis[(xx-1)*m+yy]) dfs(xx,yy);
	}
}
bool cmp(char *a,int n,int m,int x,int y){
	if(x==y) return 1;
	if(x>m||y>m) return 0;
	if(x<1||y<1) return 0;
	for(int i=1;i<=n;i++) if(a[(i-1)*m+x]!=a[(i-1)*m+y]) return 0;
	return 1;
}
void sol(char *a,int n,int m,int *l,int *r){
	static int c[2000010],t,mnc[2000010],f[1000010];
	t=0;
	for(int j=1;j<=m;j++) c[++t]=-1,c[++t]=j;
	c[++t]=-1,c[++t]=1e9,c[t+1]=0;
	for(int i=1,p,r=0;i<=t;i++){
		if(r>=i) mnc[i]=min(mnc[2*p-i],r-i+1);
		else mnc[i]=0;
		while(i-mnc[i]>=1&&i+mnc[i]<=t&&cmp(a,n,m,c[i-mnc[i]],c[i+mnc[i]])) mnc[i]++;
		if(i+mnc[i]-1>r) p=i,r=i+mnc[i]-1;
	}
	l[1]=f[1]=1,f[0]=0;
	for(int j=2;j<=m;j++){
		int p=mnc[2*j-1]/2;
		l[j]=(f[j-1]-f[j-p-1]>0);
		f[j]=f[j-1]+l[j];
	}
	r[m]=f[m]=1,f[m+1]=0;
	for(int j=m-1;j>=1;j--){
		int p=mnc[2*j+1]/2;
		r[j]=(f[j+1]-f[j+p+1]>0);
		f[j]=f[j+1]+r[j];
	}
}
void sol(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%s",a+1+(i-1)*m);
		for(int j=1;j<=m;j++) b[(j-1)*n+i]=a[(i-1)*m+j],vis[(i-1)*m+j]=0;
		ad[i].clear(),dl[i].clear();
	}
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[(i-1)*m+j]=='0'&&!vis[(i-1)*m+j]){
		X=Y=i,L=R=j,dfs(i,j);
		ad[X].push_back({L,R});
		dl[Y].push_back({L,R});
//		cerr<<"("<<X<<","<<Y<<")x("<<L<<","<<R<<")\n";
	}
	sol(a,n,m,l,r),sol(b,m,n,x,y);
//	for(int j=1;j<=m;j++) cout<<l[j]<<" ";puts("");
//	for(int j=1;j<=m;j++) cout<<r[j]<<" ";puts("");
//	for(int i=1;i<=n;i++) cout<<x[i]<<" ";puts("");
//	for(int i=1;i<=n;i++) cout<<y[i]<<" ";puts("");
	for(int j=m,x=m;j>=1;j--){
		if(r[j]) x=j;
		lst[j]=x;
	}
	int ans=2e9;
	Lt.clr(),Rt.clr();
	for(int i=1,j=1;i<=n;i++){
		while(j<=n&&(!y[j-1]||j<=i)){
			for(seg &l:ad[j]) Lt.add(l.l,1),Rt.add(l.r,1);
			j++;
		}
		if(x[i]){
			for(int k=1;k<=m;k++) if(l[k]){
				int r=lst[k],w=Lt.qry(m)-Rt.qry(k-1)-(Lt.qry(m)-Lt.qry(r));
				ans=min(ans,w);
			}
		}
		for(seg &l:dl[i]) Lt.add(l.l,-1),Rt.add(l.r,-1);
	}
	printf("%d\n",ans);
}
int main(){
	int _;
	scanf("%d",&_);
	while(_--) sol();
}