#include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #define inf (1LL<<50)

 #define pa pair<int,int>

 #define ll long long

 #define p(x,y) (x-1)*m+y

 using namespace std;

 int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 ll s0,s1;

 int c0,c1;

 int test,n,m,cnt,S,T;

 int xx[]={,,,-},yy[]={,-,,};

 int a[][];

 int last[],h[],q[],cur[];

 bool color[][];

 struct edge{

     int to,next;ll v;

 }e[];

 void insert(int u,int v,ll w)

 {

     e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;

     e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=;

 }

 bool bfs()

 {

     int head=,tail=;

     memset(h,-,sizeof(h));

     q[]=S;h[S]=;

     while(head!=tail)

     {

         int now=q[head];head++;

         for(int i=last[now];i;i=e[i].next)

             if(e[i].v&&h[e[i].to]==-)

             {

                 h[e[i].to]=h[now]+;

                 q[tail++]=e[i].to;

             }

     }

     return h[T]!=-;

 }

 ll dfs(int x,ll f)

 {

     if(x==T)return f;

     ll w,used=;

     for(int i=cur[x];i;i=e[i].next)

         if(h[e[i].to]==h[x]+)

         {

             w=dfs(e[i].to,min(f-used,e[i].v));

             e[i].v-=w;e[i^].v+=w;

             if(e[i].v)cur[x]=i;

             used+=w;if(used==f)return f;

         }

     if(!used)h[x]=-;

     return used;

 }

 ll dinic()

 {

     ll tmp=;

     while(bfs())

     {

         for(int i=S;i<=T;i++)cur[i]=last[i];

         tmp+=dfs(S,inf);

     }

     return tmp;

 }

 bool check(ll x)

 {

     memset(last,,sizeof(last));

     cnt=;S=;T=n*m+;

     ll tot=;

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++)

             if(color[i][j])

             {

                 insert(S,p(i,j),x-a[i][j]);tot+=x-a[i][j];

                 for(int k=;k<;k++)

                 {

                     int nowx=i+xx[k],nowy=j+yy[k];

                     if(nowx<||nowy<||nowx>n||nowy>m)continue;

                     insert(p(i,j),p(nowx,nowy),inf);

                 }

             }

             else insert(p(i,j),T,x-a[i][j]);

     if(dinic()==tot)return ;

     return ;

 }

 int main()

 {

     test=read();

     while(test--)

     {

         c0=c1=s0=s1=;

         n=read();m=read();

         int mx=;

         for(int i=;i<=n;i++)

             for(int j=;j<=m;j++)

             {

                 a[i][j]=read(),color[i][j]=(i+j)&;

                 mx=max(mx,a[i][j]);

             }

         for(int i=;i<=n;i++)

             for(int j=;j<=m;j++)

                 if(color[i][j])s1+=a[i][j],c1++;

                 else s0+=a[i][j],c0++;

         if(c0!=c1)

         {

             ll x=(s0-s1)/(c0-c1);

             if(x>=mx)

                 if(check(x))

                 {

                     printf("%lld\n",x*c1-s1);

                     continue;

                 }

             puts("-1");

         }

         else

         {

             if(s0!=s1)

             {

                 puts("-1");

                 continue;

             }

             ll l=mx,r=inf;

             while(l<=r)

             {

                 ll mid=(l+r)>>;

                 if(check(mid))r=mid-;

                 else l=mid+;

             }

             printf("%lld\n",(ll)l*c1-s1);

         }

     }

 }