#include<bits/stdc++.h>
#define MAXN 1010
#define MAXM 5000010
#define INF 0x7f7f7f7f7f7f7f7f
using namespace std;
typedef long long ll;
struct edge{ int pre, to; ll flow; };
ll a[45][45];
edge e[MAXM << 1];
int n, m, s, t, T, tot, cnt = 1;
int head[MAXN], dis[MAXN], cur[MAXN], id[45][45];
bool vis[MAXN];
void add_edge(int u, int v, ll w){
    e[++cnt].pre = head[u]; e[cnt].to = v; e[cnt].flow = w; head[u] = cnt;
    e[++cnt].pre = head[v]; e[cnt].to = u; e[cnt].flow = 0; head[v] = cnt;
}
bool bfs(int sour, int sink){
    memset(dis, 0, sizeof(dis));
    queue<int> q; q.push(sour);
    dis[sour] = 1; cur[sour] = head[sour];
    while(!q.empty()){
        int now = q.front(); q.pop();
        if(now == sink) return true;
        for(int i = head[now]; i; i = e[i].pre){
            if(dis[e[i].to] || e[i].flow == 0) continue;
            dis[e[i].to] = dis[now] + 1;
            cur[e[i].to] = head[e[i].to];
            q.push(e[i].to);
        }
    }
    return false;
}
ll dfs(int now, ll flow, int sink){
    if(now == sink) return flow;
    ll sum = 0; vis[now] = true;
    for(int i = cur[now]; i; i = e[i].pre){
        cur[now] = i;
        if(!vis[e[i].to] && e[i].flow != 0 && dis[e[i].to] == dis[now] + 1){
            ll tmp = dfs(e[i].to, min(flow - sum, e[i].flow), sink);
            e[i].flow -= tmp;
            e[i ^ 1].flow += tmp;
            sum += tmp;
            if(sum == flow) break;
        }
    }
    vis[now] = false;
    return sum;
}
bool check(ll x){
    ll ans = 0, sum = 0; cnt = 1;
    memset(head, 0, sizeof(head));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if((i + j) % 2) continue;
            if(id[i + 1][j] != 0) add_edge(id[i][j], id[i + 1][j], INF);
            if(id[i][j + 1] != 0) add_edge(id[i][j], id[i][j + 1], INF);
            if(id[i - 1][j] != 0) add_edge(id[i][j], id[i - 1][j], INF);
            if(id[i][j - 1] != 0) add_edge(id[i][j], id[i][j - 1], INF);
        }
    }
    s = tot + 1; t = tot + 2;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            sum += x - a[i][j];
            if((i + j) % 2) add_edge(id[i][j], t, x - a[i][j]);
            else add_edge(s, id[i][j], x - a[i][j]);
        }
    }
    while(bfs(s, t)){
        ans += dfs(s, INF, t);
    }
    return ans * 2 == sum;
}
int main(){
    scanf("%d",&T);
    while(T--){
        tot = 0;
        scanf("%d%d",&n,&m);
        ll sum_odd = 0, sum_eve = 0, cnt_odd = 0, cnt_eve = 0, maxn = 0;
        memset(id, 0, sizeof(id));
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                id[i][j] = ++tot;
                scanf("%lld",&a[i][j]);
            }
        }
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                maxn = max(maxn, a[i][j]);
                if((i + j) % 2) cnt_odd++, sum_odd += a[i][j];
                else cnt_eve++, sum_eve += a[i][j];
            }
        }
        if(cnt_odd != cnt_eve){
            ll res = (sum_eve - sum_odd) / (cnt_eve - cnt_odd);
            if(res >= maxn && check(res)) printf("%lld\n",res);
            else printf("-1\n");
        }else{
            if(sum_odd != sum_eve) printf("-1\n");
            else{
                ll l = maxn, r = INF >> 1, mid, res = -1;
                while(l <= r){
                    mid = (l + r) >> 1;
                    if(check(mid)){
                        res = mid;
                        r = mid - 1;
                    }else l = mid + 1;
                }
                if(res == -1) printf("-1\n");
                else printf("%lld\n",res * cnt_odd - sum_odd);
            }
        }
    }
    return 0;
}