#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
int T,h,w;
string s;
int sit[10],f[(1<<10)][10];
vector<pair<int,int> > e[10];
int sum(int x,int p){
	cerr<<x<<" "<<p<<")))\n";
	int sum = 0;
	for(int i=0;i<w;i++){
		if(!((x >> i) & 1) && !((p >> i) & 1)) sum++;
	}
	cerr<<sum<<"???\n";
	return sum;
}
bool check(int x,int y){
	for(int i=0;i<w;i++){
		if(((x >> i) & 3) == 3 && ((y >> i) & 3) == 3) return false;
	}
	return true;
}
void solve(){
	cin >> h >> w;
	for(int i=1;i<=h;i++){
		cin >> s;
		for(int j=0;j<s.size();j++){
			if(s[j]=='.') sit[i] += (1 << j);
		}
	}
	for(int i=1;i<=h;i++){
		for(int p=0;p<(1<<w);p++){
			f[p][i] = INT_MAX;
			if(!(sit[i] & p)) e[i].push_back({p,sum(sit[i],p)});
		}
	}
	for(auto x : e[1]){
		f[x.fi][1] = x.se;
	}
	for(int i=2;i<=h;i++){
		for(auto x : e[i]){
			for(auto y : e[i - 1]){
				if(check(x.fi,y.fi)){
					f[x.fi][i] = min(f[x.fi][i],f[y.fi][i-1] + x.se);
				}
			}
		}
	}
	int ans = INT_MAX;
	for(auto x : e[h]){
		ans = min(ans,f[x.fi][h]);
	}
	cout << ans << "\n";
	memset(sit,0,sizeof sit);
	for(int i=1;i<=9;i++){
		e[i].clear();
	}
}
int main(){
	cin >> T;
	while(T--){
		solve();
	}
	return 0;
}