#include <iostream>
#include <cstdio>
#include <queue> 
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 705;
const int inf = 0x3f3f3f3f;

struct Edge {
	int to, val, cst, rev;
	Edge (int _to = 0, int _val = 0, int _cst = 0, int _rev = 0) :
		to(_to), val(_val), cst(_cst), rev(_rev) {} 
};
vector<Edge> e[N];
void add(int u, int v, int w, int c) {
//	cout << u << " " << v << " " << w << " " << c << endl;
	e[u].push_back(Edge(v, w, c, (int)e[v].size()));
	e[v].push_back(Edge(u, 0, -c, (int)e[u].size() - 1));
}

int d[N] = {0};
bool inq[N] = {false};
bool bfs(int s, int t) {
	memset(d, ~inf, sizeof d);
	queue<int> q;
	q.push(s), d[s] = 0, inq[s] = true;
	while (!q.empty()) {
		int h = q.front();
		q.pop();
		inq[h] = false;
		for (auto i: e[h])
			if (i.val > 0 && d[i.to] < d[h] + i.cst) {
				d[i.to] = d[h] + i.cst;
				if (!inq[i.to])
					inq[i.to] = true, q.push(i.to);
			}
	}
	return d[t] > 0;
}

int cur[N] = {0};
bool vis[N] = {false};
int dfs(int x, int t, int f) {
	if (x == t)
		return f;
	int fl = 0;
	vis[x] = true;
	for (int i = cur[x]; i < (int)e[x].size(); i = ++cur[x])
		if (!vis[e[x][i].to] && e[x][i].val > 0 && d[e[x][i].to] == d[x] + e[x][i].cst) {
			fl = dfs(e[x][i].to, t, min(f, e[x][i].val));
			if (fl > 0) {
				e[x][i].val -= fl;
				e[e[x][i].to][e[x][i].rev].val += fl;
				break;
			}
		}	
	if (fl == 0)
		d[x] = -1;
	vis[x] = false;
	return fl;
}

int Dinic(int S, int T) {
	int ans = 0;
	while (bfs(S, T)) {
		memset(cur, 0, sizeof cur);
		int ad = 0;
		while ((ad = dfs(S, T, inf)) > 0)
			ans += ad * d[T];
	}
	return ans;
}

int n, m;
char mp[55][55];

int id1(int x, int y) {
	return (x - 1) * m + y;
}
int id2(int x, int y) {
	return (x - 1) * (m + 1) + y;
}

void slv() {
	cin >> n >> m;
	for (int i = 0; i <= m + 1; i++)
		mp[0][i] = mp[n + 1][i] = '.';
	for (int i = 0; i <= n + 1; i++)
		mp[i][0] = mp[i][m + 1] = '.';
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> mp[i][j];
	int S = 0, T = n * m + n * (m + 1) + (n + 1) * m + 1; 
	for (int i = S; i <= T; i++)
		e[i].clear();
	for (int i = 1; i <= n; i++) 
		for (int j = 1; j <= m; j++) 
			if (mp[i][j] == '?')
				add(S, id1(i, j), 4, 0);
	int ans = 0;
	for (int i = 1; i <= n + 1; i++)
		for (int j = 1; j <= m; j++) {
			if (i <= n && mp[i][j] == '?')
				add(id1(i, j), n * m + id1(i, j), 1, 0);
			if (i >= 2 && mp[i - 1][j] == '?')
				add(id1(i - 1, j), n * m + id1(i, j), 1, 0);
			if ((mp[i][j] == '?') + (mp[i - 1][j] == '?') == 0) {
				if ((mp[i][j] == '#') + (mp[i - 1][j] == '#') == 1)
					ans++;
			}
			else {
				if ((mp[i][j] == '?') + (mp[i - 1][j] == '?') == 2) {
					add(n * m + id1(i, j), T, 1, 1);
					add(n * m + id1(i, j), T, 1, -1);	 
				}
				else if ((mp[i][j] == '#') + (mp[i - 1][j] == '#') == 1) {
					ans++;
					add(n * m + id1(i, j), T, 1, -1);
				}
				else
					add(n * m + id1(i, j), T, 1, 1);
			}
		}
	cout << ans << endl;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m + 1; j++) {
			if (j <= m && mp[i][j] == '?')
				add(id1(i, j), n * m + (n + 1) * m + id2(i, j), 1, 0);
			if (j >= 2 && mp[i][j - 1] == '?')
				add(id1(i, j - 1), n * m + (n + 1) * m + id2(i, j), 1, 0);
			if ((mp[i][j] == '?') + (mp[i][j - 1] == '?') == 0) {
				if ((mp[i][j] == '#') + (mp[i][j - 1] == '#') == 1)
					ans++;
			}
			else {
				if ((mp[i][j] == '?') + (mp[i][j - 1] == '?') == 2) {
					add(n * m + (n + 1) * m + id2(i, j), T, 1, 1);
					add(n * m + (n + 1) * m + id2(i, j), T, 1, -1);	 
				}
				else if ((mp[i][j] == '#') + (mp[i][j - 1] == '#') == 1) {
					ans++;
					add(n * m + (n + 1) * m + id2(i, j), T, 1, -1);
				}
				else
					add(n * m + (n + 1) * m + id2(i, j), T, 1, 1);
			}
		}
	cout << Dinic(S, T) + ans << endl;
}

int main() {
	int T;
	cin >> T;
	while (T--)
		slv();
	return 0;
}

/*
1
3 3
.?.
.?.
.#.
*/