#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<algorithm>#define maxn 45#define maxv 1700#define maxe 1000500#define inf (1LL<<50)using namespace std;long long tt,n,m,map[maxn][maxn],col[maxn][maxn],n1=0,n2=0,s1=0,s2=0,mx=0;long long dx[]={0,0,1,0,-1},dy[]={0,1,0,-1,0};long long dis[maxv],nume=1,g[maxv],s,t;queue <long long> q;bool vis[maxv];struct edge{    long long v,f,nxt;}e[maxe];long long p(long long x,long long y){    return (x-1)*m+y;}void addedge(long long u,long long v,long long f){    e[++nume].v=v;e[nume].f=f;e[nume].nxt=g[u];g[u]=nume;    e[++nume].v=u;e[nume].f=0;e[nume].nxt=g[v];g[v]=nume;}bool checks(long long x,long long y){    if ((x>=1) && (x<=n) && (y>=1) && (y<=m)) return true;    return false;}void build(long long x){    nume=1;memset(g,0,sizeof(g));    s=0;t=n1+n2+1;    for (long long i=1;i<=n;i++)         for (long long j=1;j<=m;j++)        {            long long now=p(i,j);            if (col[i][j]) addedge(s,now,x-map[i][j]);            else addedge(now,t,x-map[i][j]);            if (col[i][j])            {                for (long long k=1;k<=4;k++)                {                    long long a=i+dx[k],b=j+dy[k],ret=p(a,b);                    if (checks(a,b)) addedge(now,ret,inf);                }            }        }}bool bfs(){    for (long long i=s;i<=t;i++) {dis[i]=inf;vis[i]=false;}    q.push(s);dis[s]=0;vis[s]=true;    while (!q.empty())    {        long long head=q.front();q.pop();        for (long long i=g[head];i;i=e[i].nxt)        {            long long v=e[i].v;            if ((e[i].f) && (dis[v]>dis[head]+1))            {                dis[v]=dis[head]+1;                if (!vis[v]) {q.push(v);vis[v]=true;}            }        }    }    if (dis[t]==inf) return false;    return true;}long long dinic(long long x,long long low){    if (x==t) return low;    long long ret=0;    for (long long i=g[x];i && low;i=e[i].nxt)    {        long long v=e[i].v;        if ((e[i].f) && (dis[v]==dis[x]+1))        {            long long dd=dinic(v,min(e[i].f,low));            e[i].f-=dd;e[i^1].f+=dd;            ret+=dd;low-=dd;        }    }    if (!ret) dis[x]=inf;    return ret;}bool check(long long x){    build(x);    long long max_flow=0,ret=0;    while (bfs())        max_flow+=dinic(s,inf);    for (long long i=1;i<=n;i++)        for (long long j=1;j<=m;j++)            if (col[i][j]) ret+=(x-map[i][j]);    if (ret==max_flow) return true;    return false;}void work1(){    long long x=(s1-s2)/(n1-n2);    if (x>=mx)        if (check(x))        {            long long ret=x*(n1+n2)-s1-s2;            printf("%lld\n",(x*(n1+n2)-s1-s2)/2);            return;        }    printf("-1\n");}void work2(){    if (s1!=s2) {printf("-1\n");return;}    long long l=mx,r=inf,ans=inf;    while (l<=r)    {        long long mid=l+r>>1;        if (check(mid)) {ans=mid;r=mid-1;}        else l=mid+1;    }    if (ans==inf) printf("-1\n");    else printf("%lld\n",(ans*(n1+n2)-s1-s2)/2);    return;}void work(){    n1=0;n2=0;s1=0;s2=0;mx=0;    scanf("%lld%lld",&n,&m);    for (long long i=1;i<=n;i++)        for (long long j=1;j<=m;j++)        {            scanf("%lld",&map[i][j]);            mx=max(mx,map[i][j]);        }    if ((n==1) && (m==1))     {        printf("0\n");        return;    }    col[1][1]=1;    for (long long i=1;i<=n;i++)        for (long long j=1;j<=m;j++)            for (long long k=1;k<=4;k++)                col[i+dx[k]][j+dy[k]]=col[i][j]^1;    for (long long i=1;i<=n;i++)        for (long long j=1;j<=m;j++)        {            if (col[i][j]) {n1++;s1+=map[i][j];}            else {n2++;s2+=map[i][j];}        }    if (n1!=n2) work1();    else work2();}int main(){    scanf("%lld",&tt);    for (long long i=1;i<=tt;i++)        work();    return 0;}