#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <bitset>
#include <ctime>
#include <algorithm>
using namespace std;

#define FOR(i,a,b) for (int i = a; i < b; ++i)

#define sz 2601

vector< bitset<sz> > p;
int a[55][55];

int abs(int x) {
	return x >= 0 ? x : -x;
}

int gcd(int a, int b) {
	return b ? gcd(b, a % b) : a;
}

bool in(int x, int y, int n, int m) {
	return x >= 0 && x < n && y >= 0 && y < m;
}

int init(int n, int m) {
	p.clear(); bitset<sz> cur;
	FOR(i, 0, n) FOR(j, 0, m) FOR(ii, i + 1, n) FOR(jj, 0, m) {
		if (jj == j) continue;
		int g = gcd(ii - i, abs(jj - j));
		if (g != 1 || in(i - g, j - g, n, m)) continue;
		bool ok = true;
		cur.reset();
		int x = i, y = j, dx = ii - i, dy = jj - j;
		while (in(x, y, n, m)) {
			if (a[x][y] == 0) {
				ok = false;
				break;
			}
			cur[x * n + y] = 1;
			x += dx, y += dy;
		}
		if (ok && cur.count() >= 3) p.push_back(cur);
	}
	FOR(i, 0, n) {
		cur.reset();
		bool ok = true;
		FOR(j, 0, m) {
			if (a[i][j] == 0) { ok = false; break; }
			cur[i * n + j] = 1;
		}
		if (ok && cur.count() >= 3) p.push_back(cur);
	}
	FOR(j, 0, m) {
		cur.reset();
		bool ok = true;
		FOR(i, 0, n) {
			if (a[i][j] == 0) { ok = false; break; }
			cur[i * n + j] = 1;
		}
		if (ok && cur.count() >= 3) p.push_back(cur);
	}
	return p.size();
}

int solve(int n, int m, int tot) {
	int ans = 0;
	random_shuffle(p.begin(), p.end());
	while (true) {
		bitset<sz> cur;
		cur.reset();
		FOR(i, 0, n) FOR(j, 0, m) if (a[i][j]) cur[i * n + j] = 1;
		if (cur.count() == 0) break;
		int id = -1, num = -1;
		FOR(i, 0, tot) {
			int now = (cur & p[i]).count();
			if (now != p[i].count() || now <= num) continue;
			num = now, id = i;
		}
		//cout << id << " " << num << endl;
		if (id == -1) return -1;
		FOR(i, 0, n) FOR(j, 0, m) if (p[id][i * n + j]) --a[i][j];
		++ans;
	}
	return ans;
}

int main()
{
	int t, n, m;
	scanf( "%d", &t );
	while (t--) {
		scanf( "%d%d", &n, &m );
		++n, ++m;
		FOR(i, 0, n) FOR(j, 0, m) scanf( "%d", &a[i][j] );
		int tot = init(n, m);
		//cout << tot << endl;
		int ans = -1;
		while (ans == -1) ans = solve(n, m, tot);
		printf( "%d\n", ans );
	}
	return 0;
}