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