Blinker最近喜欢上一个奇怪的游戏。
这个游戏在一个 N*M 的棋盘上玩，每个格子有一个数。每次 Blinker 会选择两个相邻
的格子，并使这两个数都加上 1。
现在 Blinker 想知道最少多少次能使棋盘上的数都变成同一个数，如果永远不能变成同
一个数则输出-1。

输入的第一行是一个整数T，表示输入数据有T轮游戏组成。
每轮游戏的第一行有两个整数N和M， 分别代表棋盘的行数和列数。
接下来有N行，每行 M个数。

对于每个游戏输出最少能使游戏结束的次数，如果永远不能变成同一个数则输出-1。

2
2 2
1 2
2 3
3 3
1 2 3
2 3 4
4 3 2

2
-1

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<vector>

#include<queue>

#include<algorithm>

#include<map>

#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

        {

            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);

        }

    }

    return ;

}