#include <bits/stdc++.h>
using namespace std;
#define MAX 400000
#define ll long long
struct E {
    ll u, v, value;
    E(ll a = 0, ll b = 0, ll c = 0) : u(a), v(b), value(c) {}
    bool operator<(E x) { return (value > x.value); }
};
ll road[MAX];
ll fnd(ll x) { return (x == road[x]) ? x : road[x] = fnd(road[x]); }
void merge(ll u, ll v) { road[fnd(u)] = fnd(v); }
int main() {
    ll T, n, m, c1, c2;
    scanf("%d", &T);
    for (ll z = 1; z <= T; ++z) {
        vector<E> q;
        scanf("%d%d", &n, &m);
        ll total = 0, ans = 0;
        for (ll i = 1; i <= n; ++i)
            for (ll j = 1; j <= m; ++j) {
                scanf("%d%d", &c1, &c2);
                total += c1 + c2;
                ll b = (i - 1) * m + j;
                if (b <= (n - 1) * m)
                    q.push_back(E(b, b + m, c1));
                if (b % m)
                    q.push_back(E(b, b + 1, c2));
            }
        sort(q.begin(), q.end());
        for (ll i = 1; i <= n * m; ++i) road[i] = i;
        for (ll i = 0; i <= n * m - 1; ++i)
            if (fnd(q[i].u) != fnd(q[i].v)) {
                merge(q[i].u, q[i].v);
                ans += q[i].value;
            }
        printf("%d\n", total - ans);
    }
    return 0;
}