Description：

棋盘每个格子有一个数。每次选择两个相邻的格子加 $1$ ，求最少多少次能使棋盘上的数都变成同一个数。

$1\leqslant n,m\leqslant 40$

Solution：

先给棋盘黑白染色，如果 $n\times m$ 是奇数，那么每加一层黑白格子数字之和变化一，因此我们可以计算出最终的高度，对于偶数的情况，由于可以密铺，因此满足单调性，可以二分这个高度，判定的话用网络流，也就是建一个黑白的二分图，每个点和周围点连边，每一个流代表一次加一操作，判断能否满流即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m;

#define MAXN 50

int a[MAXN][MAXN];

int to(int i,int j){return (i - 1) * m + j;}

int s,t;

int ch[MAXN * MAXN];

typedef long long ll;

struct edge

{

	int to,nxt;

	ll f;

}e[MAXN * MAXN * 5 * 2];

int edgenum = 0;

int lin[MAXN * MAXN] = {0};

void add(int a,int b,ll f)

{

    e[edgenum] = (edge){b,lin[a],f};lin[a] = edgenum++;

    e[edgenum] = (edge){a,lin[b],0};lin[b] = edgenum++;

    return;

}

bool BFS()

{

    memset(ch,-1,sizeof(ch));ch[s] = 0;

    queue<int> q;q.push(s);

    while(!q.empty())

    {

        int k = q.front();q.pop();

        for(int i = lin[k];i != -1;i = e[i].nxt)

        {

            if(ch[e[i].to] == -1 && e[i].f > 0)

            {

                ch[e[i].to] = ch[k] + 1;

                q.push(e[i].to);

            }

        }

    }

    return (ch[t] != -1);

}

ll flow(int k,ll f)

{

    if(k == t)return f;

    ll r = 0;

    for(int i = lin[k];i != -1 && f > r;i = e[i].nxt)

    {

        if(ch[e[i].to] == ch[k] + 1 && e[i].f > 0)

        {

            ll l = flow(e[i].to,min(e[i].f,f - r));

            e[i].f -= l;r += l;e[i ^ 1].f += l;

        }

    }

    if(r == 0)ch[k] = -1;

    return r;

}

#define INF 0x3f3f3f3f3f3f3f3f

ll ans;

ll dinic()

{

	ans = 0;ll r;

    while(BFS())while(r = flow(s,INF))ans += r;

    return ans;

}

bool check(ll h)

{

	memset(lin,-1,sizeof(lin));

	edgenum = 0;

	s = n * m + 1;t = s + 1;

	ll sum = 0;

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

	{

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

		{

			if((i + j) % 2 == 0)add(s,to(i,j),h - a[i][j]),sum += h - a[i][j];

			else add(to(i,j),t,h - a[i][j]);

			if((i + j) % 2 == 0)

			{

				if(i != 1)add(to(i,j),to(i - 1,j),INF);

				if(j != 1)add(to(i,j),to(i,j - 1),INF);

				if(i != n)add(to(i,j),to(i + 1,j),INF);

				if(j != m)add(to(i,j),to(i,j + 1),INF);

			}

		}

	}

	return sum == dinic();

}

void work()

{

	n = rd();m = rd();

	for(int i = 1;i <= n;++i)for(int j = 1;j <= m;++j)a[i][j] = rd();

	ll cur = 0;

	for(int i = 1;i <= n;++i)for(int j = 1;j <= m;++j)cur = max(cur,1ll * a[i][j]);

	ll sum0 = 0,sum1 = 0;

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

	{

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

		{

			if((i + j) % 2 == 0)sum0 += cur - a[i][j];

			else sum1 += cur - a[i][j];

		}

	}

	if(n * m % 2 != 0)

	{

		if(sum0 > sum1)puts("-1");

		else

		{

			if(check(cur + sum1 - sum0))cout << ans << endl;

			else puts("-1");

		}

	}

	else

	{

		if(sum0 != sum1)puts("-1");

		else

		{

			ll l = cur - 1,r = 10000000000000000,mid;

			while(l < r)

			{

				mid = ((l + r) >> 1);

				if(check(mid))r = mid;

				else l = mid + 1;

			}

			check(l);

			cout << ans << endl;

		}

	}

	return;

}

int main()

{

	int testcases = rd();

	while(testcases--)work();

	return 0;

}