#include <bits/stdc++.h>
using namespace std;
const int inf=1e9+9;
const int N=45;
int T,n,m,a[N][N],b,w,cnt=1;
int id(int x,int y){
	return (x-1)*m+y;
}
int head[N*N*2];
struct node{int to,nxt,w;}e[N*N*2];
void add(int u,int v,int w){
	e[++cnt].to=v;
	e[cnt].nxt=head[u];
	e[cnt].w=w;
	head[u]=cnt;
}
int dx[5]={0,0,1,0,-1};
int dy[5]={0,1,0,-1,0};
int V,s,t,deep[N*N*2],now[N*N*2];
int bfs(){
	for(int i=s;i<=t;i++)deep[i]=inf;
	deep[s]=0;
	now[s]=head[s];
	queue<int>q;
	q.push(s);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=head[u];~i;i=e[i].nxt){
			int v=e[i].to;
			if(e[i].w&&deep[v]==inf){
				q.push(v);
				now[v]=head[v];
				deep[v]=deep[u]+1;
				if(v==t)return 1;
			}
		}
	}
	return 0;
}
int dfs(int u,int sum){
	if(u==t)return sum;
	int k,flow=0;
	for(int i=now[u];~i&&sum;i=e[i].nxt){
		now[u]=i;
		int v=e[i].to;
		if(e[i].w&&(deep[v]==deep[u]+1)){
			k=dfs(v,min(sum,e[i].w));
			if(k==0)deep[v]=inf;
			e[i].w-=k;
			e[i^1].w+=k;
			flow+=k;
			sum-=k;
		}
	}
	return flow;
}
bool check(int x){
	memset(head,-1,sizeof(head));
	memset(now,0,sizeof(now));
	V=cnt=0;
	s=0,t=id(n,m)+1;
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			V+=x-a[i][j];
			if((i+j)%2==0){
				add(s,id(i,j),x-a[i][j]);
				add(id(i,j),s,0);
				for(int k=1;k<=4;k++){
					int xx=i+dx[k],yy=j+dy[k];
					if(xx>=1&&xx<=n&&yy>=1&&yy<=m){
						add(id(i,j),id(xx,yy),inf);
						add(id(xx,yy),id(i,j),0);
					}
				}
			}else{
				add(id(i,j),t,x-a[i][j]);
				add(t,id(i,j),0);
			}
		}
	}
	while(bfs()){
		ans+=dfs(s,inf);
	}
	if(ans==V)return 1;
	return 0;
}
int main(){
	cin>>T;
	while(T--){
		cin>>n>>m;
		b=0,w=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin>>a[i][j];
				if((i+j)%2==0)b+=a[i][j];
				else w+=a[i][j];
			}
		}
		if(n%2&&m%2){
			int x=b-w;
			if(check(x))cout<<(n*m/2+1)*x-b<<endl;
			else cout<<-1<<endl;
			continue;
		}
		if(b!=w){cout<<-1<<endl;continue;}
		int l=0,r=inf,ans=-1;
		while(l<=r){
			int mid=(l+r)>>1;
			//cout<<mid<<endl;
			if(check(mid))r=mid-1,ans=mid;
			else l=mid+1;
		}
		if(ans==-1)cout<<-1<<endl;
		else cout<<ans*(n*m/2)-b<<endl;
	}
	return 0;
}