#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)

using namespace std;

const int N=45*45, M=41*41*10, inf=1ll<<60;

int r, c, n, a1, a2, b1, b2, an, bn, s, t, dis[N], cur[N], sl, sr;
int hd[M], nxt[M], to[M], eg[M], tot=1, maxflow, fl, sig, mx, cl, cr;
int mp[N][N]; queue<int> q;

void eadd(int u,int v,int w) {
	if(u==v) return;
//	cout << "link " << u << ' ' << v << ' ' << w << '\n';
	to[++tot]=v, eg[tot]=w;
	nxt[tot]=hd[u], hd[u]=tot;
	to[++tot]=u, eg[tot]=0;
	nxt[tot]=hd[v], hd[v]=tot;
}

bool bfs() {
	up(i,1,n) dis[i]=0;
	while(q.size()) q.pop(); 
	dis[s]=1, q.push(s);
	while(q.size()) {
		int x=q.front(); q.pop();
		for(int i=hd[x]; i; i=nxt[i]) {
			int y=to[i], w=eg[i];
			if(w&&!dis[y]) {
				dis[y]=dis[x]+1, q.push(y);
				if(y==t) return 1;
			}
		}
	}
	return 0;
}

int dfs(int x,int sum) {
	if(x==t) return sum; 
	int res=0;
	for(int i=cur[x]; i&&sum; i=nxt[i]) {
		cur[x]=i;
		int y=to[i], w=eg[i];
		if(w&&dis[x]+1==dis[y]) {
			int k=dfs(y,min(sum,w));
			if(!k) dis[y]=0;
			eg[i]-=k, eg[i^1]+=k, res+=k, sum-=k;
		}
	}
	return res;
}

int get(int x,int y) { return (x-1)*c+y; }

int getflow(int op) {
	if(op<mx) return 0;
	memset(hd,0,sizeof(hd));
	memset(nxt,0,sizeof(nxt));
	memset(to,0,sizeof(to));
	memset(eg,0,sizeof(eg));
	maxflow=0, tot=1;
	up(i,1,r) up(j,1,c) {
		if((i+j)%2==1) continue;
		if(j>1) eadd(get(i,j),get(i,j-1),inf);
		if(j<c) eadd(get(i,j),get(i,j+1),inf);
		if(i>1) eadd(get(i,j),get(i-1,j),inf);
		if(i<r) eadd(get(i,j),get(i+1,j),inf);
	}
	up(i,1,r) up(j,1,c) {
		if((i+j)%2==0) eadd(s,get(i,j),op-mp[i][j]);
		else eadd(get(i,j),t,op-mp[i][j]);
	}
	while(bfs()) {
		up(i,1,n) cur[i]=hd[i];
		while(fl=dfs(s,inf)) maxflow+=fl;
	}
//	cout << "check " << maxflow << ' ' << r*c*op << '\n';
	return 2*maxflow==r*c*op-sig;
}

void mian() {
	cin >> r >> c;
	n=r*c, s=++n, t=++n, sig=mx=sl=sr=cl=cr=0;
	up(i,1,r) up(j,1,c) {
		cin >> mp[i][j], sig+=mp[i][j], mx=max(mx,mp[i][j]);
		if((i+j)%2==0) sl+=mp[i][j], cl++; else sr+=mp[i][j], cr++;
	}
	int l=mx, r=5e9, ans=-1;
	if(cl!=cr) {
		int d=(sl-sr)/(cl-cr);
		if(getflow(d)) ans=d;
	}
	else {
		while(l<=r) {
			int mid=(l+r)>>1;
			if(getflow(mid)) ans=mid, r=mid-1;
			else l=mid+1;
		}
	} 
	if(ans==-1) cout << ans << '\n';
	else cout << (r*c*ans-sig)/2 << '\n';
}

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