#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,INF=1e9;
int T,n,m,ans[N];
char str[N];

int dat[N*8],*cur;
int *a[N],*vis[N];

bool checkrow(int x,int y){
	if(!x && !y) return 1;
	if(!x || !y) return 0;
	for(int j=1;j<=m;j++)
		if(a[x][j]!=a[y][j]) return 0;
	return 1;
}
bool checkcol(int x,int y){
	if(!x && !y) return 1;
	if(!x || !y) return 0;
	for(int i=1;i<=n;i++)
		if(a[i][x]!=a[i][y]) return 0;
	return 1;
}

int s1[N],cnt1,s2[N],cnt2;
int p1[N],p2[N];

int L[N],R[N],D[N],U[N];

int fx[4][2]={{0,-1},{0,1},{-1,0},{1,0}};

int L_,R_,U_,D_;
void dfs(int x,int y){
	if(vis[x][y]) return ;
	vis[x][y]=1;
	U_=min(U_,x),D_=max(D_,x);
	L_=min(L_,y),R_=max(R_,y);
	
	for(int t=0;t<4;t++){
		int nx=x+fx[t][0],ny=y+fx[t][1];
		if(nx>=1 && nx<=n && ny>=1 && ny<=m && a[nx][ny]) dfs(nx,ny);
	}
}

struct abc{
	int typ,l,r,L,R;
}p[N];
int id;
namespace task1{
	struct def{
		int typ,x,num;
	}q[N];
	bool operator <(def X,def Y){
		if(X.x==Y.x) return X.typ<Y.typ;
		return X.x<Y.x;
	}
	
	int id,ANS[N];
	void init(){
		id=0;
	}
	void ins(int typ,int x,int num){
		q[++id]={typ,x,num};
	}
	void solve(){
		sort(q+1,q+id+1);
		for(int i=1;i<=id;i++) ANS[i]=0;
		int s=0;
		for(int i=1;i<=id;i++){
			if(q[i].typ==1) s++;
			else ANS[q[i].num]=s;
		}
	}
}
namespace task2{
	struct def{
		int typ,x,y,num;
	}q[N];
	bool operator <(def X,def Y){
		if(X.x==Y.x) return X.typ<Y.typ;
		return X.x<Y.x;
	}
	
	int c[N],lim;
	inline int lowbit(int x){
		return x & (-x);
	}
	inline void modify(int x){
		while(x<=lim) c[x]++,x+=lowbit(x);
	}
	inline int query(int x){
		int tot=0;
		while(x>0) tot+=c[x],x-=lowbit(x);
		return tot;
	}
	
	int id,ANS[N];
	void init(){
		id=0;
		for(int i=1;i<=lim;i++) c[i]=0;
	}
	void ins(int typ,int x,int y,int num){
		q[++id]={typ,x,y,num};
	}
	void solve(){
		for(int i=1;i<=id;i++) ANS[i]=0;
		sort(q+1,q+id+1);
		for(int i=1;i<=id;i++){
			if(q[i].typ==1) modify(q[i].y);
			else ANS[q[i].num]=query(q[i].y);
		}
	}
}

int main(){
	cin>>T;
	for(int T_=1;T_<=T;T_++){
		scanf("\n%d%d",&n,&m);
		task2::lim=max(n,m);
		cur=&dat[0];
		for(int i=1;i<=n;i++) a[i]=cur,cur+=m+5;
		for(int i=1;i<=n;i++) vis[i]=cur,cur+=m+5;
		
		for(int i=1;i<=n;i++){
			scanf("\n%s",str+1);
			for(int j=1;j<=m;j++){
				a[i][j]=(str[j]-'0')^1;
				vis[i][j]=0;
			}
		}
		
		if(T_==72){
			cout<<n<<" "<<m<<'\n';
			for(int i=1;i<=n;i++){
				for(int j=1;j<=m;j++) cout<<(a[i][j]^1)<<" ";
				cout<<'\n';
			}
			return 0;
		}
		
		int mx;
		cnt1=cnt2=0;
		for(int i=1;i<=n;i++) s1[++cnt1]=0,s1[++cnt1]=i;
		s1[++cnt1]=0;
		int r=-1,c=-1;
		for(int i=1;i<=cnt1;i++){
			p1[i]=1;
			if(i<=r) p1[i]=min(r-i+1,p1[2*c-i]);
			while(i-p1[i]>=1 && checkrow(s1[i-p1[i]],s1[i+p1[i]])) p1[i]++;
			if(i+p1[i]-1>r) r=i+p1[i]-1,c=i;
		}
		
		U[1]=1; mx=1;
		for(int i=2;i<=n;i++){
			int lim=i*2-1-p1[i*2-1]+1;
			if(lim<=2*mx) U[i]=1,mx=i;
			else U[i]=0;
		}
		D[n]=1; mx=n;
		for(int i=n-1;i>=1;i--){
			int lim=i*2+1+p1[i*2+1]-1;
			if(lim>=2*mx) D[i]=1,mx=i;
			else D[i]=0;
		}
		
		for(int i=1;i<=m;i++) s2[++cnt2]=0,s2[++cnt2]=i;
		s2[++cnt2]=0;
		r=-1,c=-1;
		for(int i=1;i<=cnt2;i++){
			p2[i]=1;
			if(i<=r) p2[i]=min(r-i+1,p2[2*c-i]);
			while(i-p2[i]>=1 && checkcol(s2[i-p2[i]],s2[i+p2[i]])) p2[i]++;
			if(i+p2[i]-1>r) r=i+p2[i]-1,c=i;
		}
		
		L[1]=1;
		mx=1;
		for(int i=2;i<=m;i++){
			int lim=i*2-1-p2[i*2-1]+1;
			if(lim<=2*mx) L[i]=1,mx=i;
			else L[i]=0;
		}
		R[m]=1; mx=m;
		for(int i=m-1;i>=1;i--){
			int lim=i*2+1+p2[i*2+1]-1;
			if(lim>=2*mx) R[i]=1,mx=i;
			else R[i]=0;
		}
		
//		for(int i=1;i<=cnt1;i++) cout<<p1[i]<<" "; cout<<'\n';
//		for(int i=1;i<=cnt2;i++) cout<<p2[i]<<" "; cout<<'\n';
//		
//		cout<<"U: "; for(int i=1;i<=n;i++) cout<<U[i]<<" "; cout<<'\n';
//		cout<<"D: "; for(int i=1;i<=n;i++) cout<<D[i]<<" "; cout<<'\n';
//		cout<<"L: "; for(int i=1;i<=m;i++) cout<<L[i]<<" "; cout<<'\n';
//		cout<<"R: "; for(int i=1;i<=m;i++) cout<<R[i]<<" "; cout<<'\n';
		D[n+1]=0;
		for(int i=n;i>=1;i--){
			if(D[i]) D[i]=i;
			else D[i]=D[i+1];
		}
		R[m+1]=0;
		for(int i=m;i>=1;i--){
			if(R[i]) R[i]=i;
			else R[i]=R[i+1];
		}
		
		id=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				if(!a[i][j] || vis[i][j]) continue;
				L_=U_=INF,R_=D_=0;
				dfs(i,j);
				p[++id]={1,U_,D_,L_,R_};
			}
		}
		int sav=id;
		
		for(int i=1;i<=n;i++){
			if(!U[i] || !D[i]) continue;
			for(int j=1;j<=m;j++){
				if(!L[j] || !R[j]) continue;
				p[++id]={2,i,D[i],j,R[j]};
			}
		}
		
//		for(int i=1;i<=id;i++){
//			cout<<" "<<p[i].typ<<" "<<p[i].l<<","<<p[i].r<<" "<<p[i].L<<" "<<p[i].R<<'\n';
//		}
		
		for(int i=1;i<=id;i++) ans[i]=0;
		
		for(int fl=0;fl<=1;fl++){
			task1::init();
			for(int i=1;i<=id;i++){
				if(p[i].typ==1) task1::ins(1,p[i].r,i);
				else task1::ins(2,p[i].l-1,i);
			}
			
			task1::solve();
			for(int i=1;i<=id;i++) ans[i]+=task1::ANS[i];
			
			for(int i=1;i<=id;i++){
				p[i].l=N-p[i].l,p[i].r=N-p[i].r;
				swap(p[i].l,p[i].r);
			}
		}
		
		for(int fl=0;fl<=1;fl++){
			task1::init();
			for(int i=1;i<=id;i++){
				if(p[i].typ==1) task1::ins(1,p[i].R,i);
				else task1::ins(2,p[i].L-1,i);
			}
			
			task1::solve();
			for(int i=1;i<=id;i++) ans[i]+=task1::ANS[i];
			
			for(int i=1;i<=id;i++){
				p[i].L=N-p[i].L,p[i].R=N-p[i].R;
				swap(p[i].L,p[i].R);
			}
		}
		
		for(int fl1=0;fl1<=1;fl1++){
			for(int fl2=0;fl2<=1;fl2++){
				task2::init();
				
				for(int i=1;i<=id;i++){
					if(p[i].typ==1) task2::ins(1,p[i].r,p[i].R,i);
					else task2::ins(2,p[i].l-1,p[i].L-1,i);
				}
				
				task2::solve();
				for(int i=1;i<=id;i++) ans[i]-=task2::ANS[i];
				
				for(int i=1;i<=id;i++){
					p[i].L=N-p[i].L,p[i].R=N-p[i].R;
					swap(p[i].L,p[i].R);
				}
			}
			for(int i=1;i<=id;i++){
				p[i].l=N-p[i].l,p[i].r=N-p[i].r;
				swap(p[i].l,p[i].r);
			}
		}
		
		int anss=INF;
		for(int i=sav+1;i<=id;i++){
			anss=min(anss,sav-ans[i]);
//			cout<<sav-ans[i]<<" ";
		}
//		cout<<'\n';
		cout<<anss<<'\n';
	}
	
}