#include<bits/stdc++.h>
using namespace std;
#define maxn 105
#define maxm 300005
#define int long long

const int inff = 0x3f3f3f3f3f3f3f3fll;
int _t,_n,_m,_head[maxm],_cnt=1,_max,_ans,s,t,_deep[maxm];
int _num[105][105],_max1,_max2,s1,s0,c1,c0;
struct pp{
	int v,w,nt;
}_rd[maxm*4];
bool _bj[maxm];
queue<int> _mq;
int cx[5]={0,1,-1,0,0};
int cy[5]={0,0,0,1,-1};

int node(int x,int y){
	return (x-1)*_m+y;
}
void add(int a,int b,int c){
	_rd[++_cnt].v=b;
	_rd[_cnt].nt=_head[a];
	_rd[_cnt].w=c;
	_head[a]=_cnt;
	swap(a,b);
	_rd[++_cnt].v=b;
	_rd[_cnt].nt=_head[a];
	_rd[_cnt].w=0;
	_head[a]=_cnt;
}
bool bfs(){
	memset(_deep,0,sizeof(_deep));
	_mq.push(s);
	_deep[s]=1;
	while(_mq.size()){
		int x = _mq.front();
		_mq.pop();
		for(int i = _head[x];i;i=_rd[i].nt){
			int v = _rd[i].v,w = _rd[i].w;
			if(w>0&&_deep[v]==0){
				_deep[v]=_deep[x]+1;
				_mq.push(v);
			}
		}
	}
	return _deep[t]!=0;
}
int dfs(int x,int lim){
	if(x==t||!lim){
		return lim;
	}
	int tmp=0,flow=0;
	for(int i = _head[x];i;i=_rd[i].nt){
		int v = _rd[i].v;
		if(_deep[v]==_deep[x]+1&&_rd[i].w){
			tmp = dfs(v,min(lim,_rd[i].w));
			lim-=tmp;
			flow +=tmp;
			_rd[i^0].w-=tmp;
			_rd[i^1].w+=tmp;
			if(!lim)break;
		}
	}
	return flow;
}
bool pd(int x,int y){
	if(x>=1&&x<=_n&&y>=1&&y<=_m)return 1;
	return 0;
}
bool ck(int x){
	memset(_head,0,sizeof(_head));
	_cnt=1;
	int sum = 0,ans=0;
	for(int i = 1;i <= _n;i++){
		for(int j = 1;j <= _m;j++){
			if((i+j)%2==0){
				add(s,node(i,j),x-_num[i][j]);
				sum+=(x-_num[i][j]);
				for(int k = 1;k <= 4;k++){
					int chx = i +cx[k],chy =j+ cy[k];
					if(pd(chx,chy)){
						add(node(i,j),node(chx,chy),inff);
					}
				}			
			}else{
				add(node(i,j),t,x-_num[i][j]);
			}
		}
	}
	while(bfs())ans+=dfs(s,inff);
	return ans==sum;
}
signed main(){
	cin >> _t;
	while(_t--){
		cin >> _n >> _m;
		s = 0,t = _n*_m+1;
		_max=_max1=0;
		s1=s0=c1=c0=0;
		for(int i = 1;i <= _n;i++){
			for(int j = 1;j <= _m;j++){
				cin >> _num[i][j];
				_max1=max(_max1,_num[i][j]);
				if((i+j)%2){
					s1+=_num[i][j];
					c1++;
				}else{
					s0+=_num[i][j];
					c0++;
				}
			}
		}	
		if(c1!=c0){
			int x = (s0-s1)/(c0-c1);
			if(x>=_max1&&ck(x)){
				cout << x*c1-s1<<endl;
			}else{
				cout << -1 << endl;
			}
		}else{
			if(s0!=s1){
				cout << -1 << endl;
				continue;
			}
			int l = _max1-1,r =1e15,mid;
			while(l+1!=r){
				mid=(l+r)/2;
				if(ck(mid)){
					_max=mid;
					r=mid;
				}else{
					l=mid;
				}
			} 
			if(r!=1e15){
				cout << _max*c1-s1 << endl;
			}else{
				cout << -1 << endl;
			}
		}
	}
	return 0;
}