#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MAXN = 2001;
const int INF = 1e9;

int a[MAXN][MAXN], n, m;
vector<pair<int, int>> masks1[MAXN], masks2[MAXN];
int dp1[MAXN][2][2], dp2[MAXN][2][2];

void reset() {
	for (int i = 1; i <= max(n, m); i++) {
		masks1[i].clear();
		masks2[i].clear();
	}
}

bool is_ok(vector<pair<int, int>> &masks, int v1, int v2, int v3) {
	for (auto [x, y] : masks) {
		if ((v1 ^ v2) != x && (v2 ^ v3) != y) return false;
	}
	return true;
}

int calc_dp(int dp[MAXN][2][2], vector<pair<int, int>> masks[MAXN], int L) {
	dp[1][0][1] = 1;
	dp[1][1][1] = 1;
	for (int i = 2; i <= L; i++) {
		for (int a = 0; a < 2; a++) {
			for (int b = 0; b < 2; b++) {
				dp[i][a][b] = INF;
				for (int c = 0; c < 2; c++) {
					for (int d = 0; d < 2; d++) {
						if (is_ok(masks[i-2], c, d, a) && is_ok(masks[i-1], d, a, b)) {
							dp[i][a][b] = min(dp[i][a][b], dp[i-2][c][d]+a+b);
						}
					}
				}
			}
		}
	}
	int res = INF;
	for (int a = 0; a < 2; a++) {
		for (int b = 0; b < 2; b++) {
			res = min(res, dp[L][a][b]);
		}
	}
	return res;
}

void solve() {
	cin >> n >> m;
	reset();
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			char c; cin >> c;
			a[i][j] = c == '1';
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 2; j < m; j++) {
			masks1[j].emplace_back(a[i][j-1] == a[i][j], a[i][j] == a[i][j+1]);
		}
	}
	for (int i = 2; i < n; i++) {
		for (int j = 1; j <= m; j++) {
			masks2[i].emplace_back(a[i-1][j] == a[i][j], a[i][j] == a[i+1][j]);
		}
	}
	for (int i = 1; i <= max(n, m); i++) {
		{
			auto &v = masks1[i];
			sort(v.begin(), v.end());
			v.erase(unique(v.begin(), v.end()), v.end());
		}
		{
			auto &v = masks2[i];
			sort(v.begin(), v.end());
			v.erase(unique(v.begin(), v.end()), v.end());
		}
	}

	int ans1 = calc_dp(dp1, masks1, m);
	int ans2 = calc_dp(dp2, masks2, n);
	cout << (ans1+ans2>=INF ? -1 : ans1 + ans2) << "\n";

}

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--) solve();
	return 0;
}