#include <bits/stdc++.h>
#define db double
#define il inline
#define re register
#define ll long long
#define ui unsigned
#define ull ui ll
#define i128 __int128
#define pii pair<int, int>
#define fi first
#define se second
#define eb emplace_back
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define mems(v, x) memset(v, x, sizeof(v))
#define memc(a, b) memcpy(a, b, sizeof(a))
#define FOR(i, L, R) for(re int i = (L); i <= (R); ++i)
#define ROF(i, R, L) for(re int i = (R); i >= (L); --i)
#define LS i << 1, l, mid
#define RS i << 1 | 1, mid + 1, r
#define popc(x) __builtin_popcount(x)
using namespace std;
#define N 105
#define M 2000005
#define P 998244353
il int add(int x, int y) {return x + y < P ? x + y : x + y - P;}
il void addr(int &x, int y) {(x += y) >= P && (x -= P);}
il int qpow(int p, int n = P - 2) {
  int s = 1;
  while(n) {
    if(n & 1) s = 1ll * s * p % P;
    p = 1ll * p * p % P, n >>= 1;
  }
  return s;
}
int S, T;
struct edge {
  int next, to, v;
} e[M];
int cnt, head[M];
il void add(int x, int y, int v) {
  e[++cnt] = {head[x], y, v}, head[x] = cnt;
  e[++cnt] = {head[y], x, 0}, head[y] = cnt;
}
int d[M], cur[M];
il bool bfs() {
  FOR(i, 0, T) d[i] = 0, cur[i] = head[i];
  queue<int> Q; Q.emplace(S), d[S] = 1;
  while(!Q.empty()) {
    int x = Q.front(); Q.pop();
    for(re int i = head[x]; i; i = e[i].next) {
      int y = e[i].to; if(!d[y] && e[i].v) {
        d[y] = d[x] + 1; if(y == T) return 1; Q.emplace(y);
      }
    }
  }
  return 0;
}
il int dfs(int x, int flow) {
  if(x == T) return flow; int s = 0;
  for(re int i = cur[x]; i; i = e[i].next) {
    int y = e[i].to; cur[x] = i; if(d[y] == d[x] + 1 && e[i].v) {
      int v = dfs(y, min(flow, e[i].v)); flow -= v, s += v;
      e[i].v -= v, e[i ^ 1].v += v; if(!flow) break;
    }
  }
  return s;
}
il int dinic() {
  int s = 0, v;
  while(bfs()) while(v = dfs(S, 1e9)) s += v;
  return s;
}
int n, m;
string s[N];
int L[N][N], R[N][N];
il void WORK() {
  cin >> n >> m;
  FOR(i, 1, n) {
    cin >> s[i], s[i] = " " + s[i];
    FOR(j, 1, m) if((i + j & 1) && s[i][j] != '?') s[i][j] ^= 1;
  }
  FOR(i, 0, T) head[i] = 0; cnt = 1, T = 0; int A = 0;
  FOR(i, 1, n - 1) FOR(j, 1, m - 1) L[i][j] = ++T, R[i][j] = ++T; ++T;
  FOR(i, 1, n - 1) FOR(j, 1, m - 1) {
    int c = 0;
    if(s[i][j] != '1' && s[i][j + 1] != '1' && s[i + 1][j] != '1' && s[i + 1][j + 1] != '1') ++c, add(S, L[i][j], 1);
    if(s[i][j] != '1' && s[i][j + 1] != '1' && s[i + 1][j] != '1' && s[i + 1][j + 1] != '1') ++c, add(R[i][j], T, 1);
    if(c) add(L[i][j], R[i][j], c); A += c;
  }
  FOR(i, 1, n - 1) FOR(j, 1, m - 1) {
    if(i > 1) add(L[i][j], R[i - 1][j], 1e9), add(L[i - 1][j], R[i][j], 1e9);
    if(j > 1) add(L[i][j], R[i][j - 1], 1e9), add(L[i][j - 1], R[i][j], 1e9);
    if(i > 1 && j > 1) add(L[i][j], R[i - 1][j - 1], 1e9), add(L[i - 1][j - 1], R[i][j], 1e9);
  }
  cout << A - dinic() << "\n";
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int T; cin >> T;
  while(T--) WORK();
  cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
  return 0;
}