#ifdef D
#include "hpp.hpp"
#else
#include <bits/stdc++.h>
#endif

using namespace std;

using I = long long;

class Main {
    struct C {
        I c;
        I x;
        I y;

        bool operator<(C const &t) const { return c < t.c; }
    };

    vector<C> cs;
    vector<I> ds;
    I const M, M1, N, N1;

    I find(I i) { return i == ds[i] ? i : ds[i] = find(ds[i]); }
    inline bool merge(I i, I j) {
        I const fi = find(i), fj = find(j);
        if (fi == fj) {
            return false;
        }
        ds[fj] = fi;
        return true;
    }

public:
    Main(I m, I n) : M(m), M1(m + 1), N(n), N1(n + 1) {
        cs.resize(M * N << 1);
        ds.resize(M1 * N1, 0);
        I i, j, t = 0, u, v, w = M1;
        for (i = 1; i <= N; ++i) {
            ++w;
            for (j = 1; j <= M; ++j, ++w) {
                scanf("%lld%lld", &u, &v);
                cs[t++] = { u, w - 1, w };
                cs[t++] = { v, w - M1, w };
                ds[w] = w;
            }
        }
        for (i = 1; i <= N; ++i) {
            ds[i * M1 + M] = 0;
        }
        for (j = 1; j <= M; ++j) {
            ds[N * M1 + j] = 0;
        }
    }

    void main() {
        I s = 0, z = (M - 1) * (N - 1);
        sort(cs.begin(), cs.end());
        for (C const &c : cs) {
            if (!z) {
                printf("%lld\n", s);
                return;
            }
            if (merge(c.x, c.y)) {
                s += c.c;
                --z;
            }
        }
    }
};

int main() {
    I m, n, t;
    for (scanf("%lld", &t); t; --t) {
        scanf("%lld%lld", &n, &m);
        Main main(m, n);
        main.main();
    }
}

/sandbox/1/a.cpp:9:7: error: expected nested-name-specifier before 'I'
 using I = long long;
       ^
/sandbox/1/a.cpp:13:9: error: 'I' does not name a type
         I c;
         ^
/sandbox/1/a.cpp:14:9: error: 'I' does not name a type
         I x;
         ^
/sandbox/1/a.cpp:15:9: error: 'I' does not name a type
         I y;
         ^
/sandbox/1/a.cpp:21:12: error: 'I' was not declared in this scope
     vector<I> ds;
            ^
/sandbox/1/a.cpp:21:13: error: template argument 1 is invalid
     vector<I> ds;
             ^
/sandbox/1/a.cpp:21:13: error: template argument 2 is invalid
/sandbox/1/a.cpp:22:5: error: 'I' does not name a type
     I const M, M1, N, N1;
     ^
/sandbox/1/a.cpp:24:5: error: 'I' does not name a type
     I find(I i) { return i == ds[i] ? i : ds[i] = find(ds[i]); }
     ^
/sandbox/1/a.cpp:25:23: error: 'I' has not been declared
     inline bool merge(I i, I j) {
                       ^
/sandbox/1/a.cpp:25:28: error: 'I' has not been declared
     inline bool merge(I i, I j) {
                            ^
/sandbox/1/a.cpp:35:11: error: expected ')' before 'm'
     Main(I m, I n) : M(m), M1(m + 1), N(n), N1(n + 1) {
         ~ ^~
           )
/sandbox/1/a.cpp: In member function 'bool Main::C::operator<(const Main::C&) const':
/sandbox/1/a.cpp:17:51: error: 'c' was not declared in this scope
         bool operator<(C const &t) const { return c < t.c; }
                                                   ^
/sandbox/1/a.cpp:17:51: note: suggested alternative: 'cs'
         bool operator<(C const &t) const { return c < t.c; }
                                                   ^
                                                   cs
/sandbox/1/a.cpp:17:57: error: 'const struct Main::C' has no member named 'c'
         bool operator<(C const &t) const { return c < t.c; }
                                                         ^
/sandbox/1/a.cpp: In member function 'bool Main::merge(int, int)':
/sandbox/1/a.cpp:26:9: error: 'I' was not declared in this scope
         I const fi = find(i), fj = find(j);
         ^
/sandbox/1/a.cpp:27:13: error: 'fi' was not declared in this scope
         if (fi == fj) {
             ^~
/sandbox/1/a.cpp:27:13: note: suggested alternative: 'i'
         if (fi == fj) {
             ^~
             i
/sandbox/1/a.cpp:27:19: error: 'fj' was not declared in this scope
         if (fi == fj) {
                   ^~
/sandbox/1/a.cpp:27:19: note: suggested alternative: 'j'
         if (fi == fj) {
                   ^~
                   j
/sandbox/1/a.cpp:30:12: error: 'fj' was not declared in this scope
         ds[fj] = fi;
            ^~
/sandbox/1/a.cpp:30:12: note: suggested alternative: 'j'
         ds[fj] = fi;
            ^~
            j
/sandbox/1/a.cpp:30:18: error: 'fi' was not declared in this scope
         ds[fj] = fi;
                  ^~
/sandbox/1/a.cpp:30:18: note: suggested alternative: 'i'
         ds[fj] = fi;
                  ^~
                  i
/sandbox/1/a.cpp: In member function 'void Main::main()':
/sandbox/1/a.cpp:57:9: error: 'I' was not declared in this scope
         I s = 0, z = (M - 1) * (N - 1);
         ^
/sandbox/1/a.cpp:59:27: warning: range-based 'for' loops only available with -std=c++11 or -std=gnu++11
         for (C const &c : cs) {
                           ^~
/sandbox/1/a.cpp:59:27: error: forming reference to reference type 'std::vector<Main::C>&'
/sandbox/1/a.cpp:60:18: error: 'z' was not declared in this scope
             if (!z) {
                  ^
/sandbox/1/a.cpp:61:34: error: 's' was not declared in this scope
                 printf("%lld\n", s);
                                  ^
/sandbox/1/a.cpp:61:34: note: suggested alternative: 'cs'
                 printf("%lld\n", s);
                                  ^
                                  cs
/sandbox/1/a.cpp:64:25: error: 'const struct Main::C' has no member named 'x'
             if (merge(c.x, c.y)) {
                         ^
/sandbox/1/a.cpp:64:30: error: 'const struct Main::C' has no member named 'y'
             if (merge(c.x, c.y)) {
                              ^
/sandbox/1/a.cpp:65:17: error: 's' was not declared in this scope
                 s += c.c;
                 ^
/sandbox/1/a.cpp:65:17: note: suggested alternative: 'cs'
                 s += c.c;
                 ^
                 cs
/sandbox/1/a.cpp:65:24: error: 'const struct Main::C' has no member named 'c'
                 s += c.c;
                        ^
/sandbox/1/a.cpp:66:19: error: 'z' was not declared in this scope
                 --z;
                   ^
/sandbox/1/a.cpp: In function 'int main()':
/sandbox/1/a.cpp:73:5: error: 'I' was not declared in this scope
     I m, n, t;
     ^
/sandbox/1/a.cpp:74:25: error: 't' was not declared in this scope
     for (scanf("%lld", &t); t; --t) {
                         ^
/sandbox/1/a.cpp:74:25: note: suggested alternative: 'tm'
     for (scanf("%lld", &t); t; --t) {
                         ^
                         tm
/sandbox/1/a.cpp:75:28: error: 'n' was not declared in this scope
         scanf("%lld%lld", &n, &m);
                            ^
/sandbox/1/a.cpp:75:28: note: suggested alternative: 'yn'
         scanf("%lld%lld", &n, &m);
                            ^
                            yn
/sandbox/1/a.cpp:75:32: error: 'm' was not declared in this scope
         scanf("%lld%lld", &n, &m);
                                ^
/sandbox/1/a.cpp:75:32: note: suggested alternative: 'tm'
         scanf("%lld%lld", &n, &m);
                                ^
                                tm