#include <stdio.h>
#include <queue>

using namespace std;

int h, w;

const int SSS = 2147483647;
const int TTT = -2147483648;
int N, M, oddNum, evenNum;
int oddRow[204], oddCol[204], evenRow[204], evenCol[204];
int bh[50][50] = {0};
int graph[204][204] = {{0}};
bool s[204] = {false}, t[204] = {false};//false表示可用

void init(){
	for(int i = 0; i < 204; i++)
		for(int j = 0; j < 204; j++)
			graph[i][j] = 0;
	for(int i = 0; i < 204; i++) s[i] = 0;
	for(int i = 0; i < 204; i++) t[i] = 0;
	for(int i = 0; i < 50; i++)
		for(int j = 0; j < 50; j++)
			bh[i][j] = 0;
	oddNum = 0, evenNum = 0;
}

bool pushflow(){
	//如果push不了，返回false
	queue<int> bfs;
	bool getT = false;
	int noT;
	int S[204] = {0}, T[204] = {0};
	for(int i = 1; i < N; i++){
		if(!s[i]){
			S[i] = SSS;
			bfs.push(i);
		}
	}
	while(!bfs.empty()){
		int cur = bfs.front();
		bfs.pop();
		if(cur > 0){
			//是s这边的点
			for(int j = 1; j <= M; j++){
				if(graph[cur][j] == 1 && T[j] == 0){
					bfs.push(-j);
					T[j] = cur;
				}
			}
		}
		else{
			//是t这边的点
			int j = -cur;
			if(!t[j]){
				getT = true;
				noT = cur;
				break;
			}
			for(int i = 1; i < N; i++){
				if(graph[i][j] == -1 && S[i] == 0){
					bfs.push(i);
					S[i] = cur;
				}
			}
		}
	}
	if(!getT) return false;
	t[-noT] = true;
	int TtoS = 1;
	while(1){
		if(TtoS){
			//push路径当前从S端到T端
			int noS = T[-noT];
			graph[noS][-noT] = -1;
			noT = noS;
		}
		else{
			//从T端到S端
			int noS = S[noT];
			if(noS == SSS){
				s[noT] = true;
				break;
			}
			graph[noT][-noS] = 1;
			noT = noS;
		}
		TtoS = 1 - TtoS;
	}
	return true;
}

int main() {
	int cases;
	scanf("%d", &cases);
	for(int i = 0; i < cases; i++){
		scanf("%d%d", &h, &w);
		init();
		for(int j = 0; j < h; j++){
			char s[50];
			scanf("%s", s);
			for(int k = 0; k < w; k++){
				if(s[k] == '*') {
					if((j+k)%2==0){
						evenNum ++;
						bh[j][k] = evenNum;
						evenRow[evenNum] = j;
						evenCol[evenNum] = k;
						if(j > 0 && bh[j-1][k] > 0){
							graph[bh[j-1][k]][bh[j][k]] = 1;
						}
						if(k > 0 && bh[j][k-1] > 0){
							graph[bh[j][k-1]][bh[j][k]] = 1;
						}
					}
					else{
						oddNum ++;
						bh[j][k] = oddNum;
						oddRow[oddNum] = j;
						oddCol[oddNum] = k;
						if(j > 0 && bh[j-1][k] > 0){
							graph[bh[j][k]][bh[j-1][k]] = 1;
						}
						if(k > 0 && bh[j][k-1] > 0){
							graph[bh[j][k]][bh[j][k-1]] = 1;
						}
					}
				}
			}
		}
		N = oddNum + 1, M = evenNum;
		int cnt = 0;
		while(pushflow()){cnt++;}
		printf("%d\n", oddNum+evenNum-cnt);
	}
	return 0;
}