#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<list>
using namespace std;
const int MAXN=2048,MAXM=20480,MAXL=45;
int tasks,n,m;
int a[MAXN],col[MAXL][MAXL];
int head[MAXN],to[MAXM],nxt[MAXM],etot;
long long flow[MAXM];
inline void add_edge(int a,int b,long long c)
{
    //printf("add edge from %d to %d with cap = %lld\n",a,b,c);
    to[etot]=b;
    flow[etot]=c;
    nxt[etot]=head[a];
    head[a]=etot++;
}
int s,t;
int dep[MAXN];
queue<int,list<int> >q;
bool bfs()
{
    memset(dep,0,sizeof(int)*(t+10));
    while(!q.empty())
        q.pop();
    q.push(s);
    dep[s]=1;
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        for(int i=head[now];~i;i=nxt[i])
            if(!dep[to[i]]&&flow[i])
            {
                dep[to[i]]=dep[now]+1;
                q.push(to[i]);
            }
    }
    return dep[t];
}
long long dfs(int now,long long nowf)
{
    //printf("dfs(%d,%lld)\n",now,nowf);
    if(now==t)
        return nowf;
    long long used=0;
    for(int i=head[now];~i;i=nxt[i])
        if(flow[i]&&dep[to[i]]==dep[now]+1)
        {
            long long temp=dfs(to[i],min(nowf-used,flow[i]));
            if(temp)
            {
                flow[i]-=temp;
                flow[i^1]+=temp;
                //printf("edge from %d to %d,use flow %lld\n",now,to[i],temp);
                used+=temp;
                if(used==nowf)
                    break;
            }
        }
    if(used==0)
        dep[now]=0;
    return used;
}
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
long long calc(long long target_val)
{
    memset(head,0xff,sizeof(int)*(t+10));
    memset(nxt,0xff,sizeof(int)*(t*6+10));
    etot=0;
    //printf("edge cleared\n");
    long long sum1=0,sum0=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(col[i][j]==1)
            {
                long long cap=target_val-a[(i-1)*m+j];
                if(cap<0)
                    return -1;
                add_edge(s,(i-1)*m+j,cap);
                add_edge((i-1)*m+j,s,0);
                sum1+=cap;
            }
            else
            {
                long long cap=target_val-a[(i-1)*m+j];
                if(cap<0)
                    return -1;
                add_edge((i-1)*m+j,t,cap);
                add_edge(t,(i-1)*m+j,0);
                sum0+=cap;
            }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(col[i][j]==1)
            {
                for(int k=0;k<4;k++)
                {
                    int nx=dx[k]+i,ny=dy[k]+j;
                    if(nx<=n&&ny<=m&&nx>0&&ny>0)
                    {
                        add_edge((i-1)*m+j,(nx-1)*m+ny,2e9);
                        add_edge((nx-1)*m+ny,(i-1)*m+j,0);
                    }
                }
            }
    if(sum0!=sum1)
        return -1;
    long long maxf=0;
    while(bfs())
        maxf+=dfs(s,2e9);
    if(maxf<sum1)
        return -1;
    return sum1;
}
int main()
{
    scanf("%d",&tasks);
    col[1][1]=1;
    for(int i=2;i<=40;i++)
        col[i][1]=col[i-1][1]^1;
    for(int j=2;j<=40;j++)
        for(int i=2;i<=40;i++)
            col[i][j]=col[i][j-1]^1;
    while(tasks--)
    {
        scanf("%d%d",&n,&m);
        s=0,t=n*m+1;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("%d",a+((i-1)*m+j));
        if(n*m%2==1)
        {
            int tval=0;
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                    if(col[i][j]==1)
                        tval+=a[(i-1)*m+j];
                    else tval-=a[(i-1)*m+j];
            if(tval<0)
                tval=-tval;
            printf("%lld\n",calc(tval));
        }
        else
        {
            long long l=1,r=2e9+7,res=-1;
            while(l<r)
            {
                long long mid=(l+r)>>1;
                //printf("l=%lld,r=%lld,mid=%lld\n",l,r,mid);
                int temp=calc(mid);
                if(temp==-1)
                    l=mid+1;
                else res=temp,r=mid-1;
            }
            printf("%lld\n",res);
        }
    }
    return 0;
}