#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<bits/stdc++.h>

using namespace __gnu_pbds;
using namespace std;

typedef tree <
int,
null_type,
less < int >,
rb_tree_tag,
tree_order_statistics_node_update > ordered_set;

typedef long long ll;
int const maxn = 25e4 + 5;
set < int > b[3];
int nxtL[maxn], nxtR[maxn];
int cmp[maxn];
ll sz[maxn], add;
int righ[(1 << 19)], lef[(1 << 19)], n;
ordered_set in[maxn];

inline void upd(int c, int x) {
    add -= sz[c] * (sz[c] - 1) / 2;
    sz[c] += x;
    add += sz[c] * (sz[c] - 1) / 2;
}

void build(int i, int l, int r) {
    if (r - l == 1) righ[i] = nxtR[l], lef[i] = nxtL[l];
    else {
        int m = (r + l) / 2;
        build(2 * i + 1, l, m);
        build(2 * i + 2, m, r);
        righ[i] = max(righ[2 * i + 1], righ[2 * i + 2]);
        lef[i] = min(lef[2 * i + 1], lef[2 * i + 2]);
    }
}

void update(int i, int l, int r, int lq) {
     if (r - l == 1) righ[i] = nxtR[l], lef[i] = nxtL[l];
    else {
        int m = (r + l) / 2;
        if (lq < m) update(2 * i + 1, l, m, lq);
        else update(2 * i + 2, m, r, lq);
        righ[i] = max(righ[2 * i + 1], righ[2 * i + 2]);
        lef[i] = min(lef[2 * i + 1], lef[2 * i + 2]);
    }
}

int getR(int i, int l, int r, int lq, int rq) {
    if (lq >= r || l >= rq || righ[i] < rq) return -1;
    if (r - l == 1) return l;
    int m = (r + l) / 2;
    int res = getR(2 * i + 1, l, m, lq, rq);
    if (res == -1) res = getR(2 * i + 2, m, r, lq, rq);
    return res;
}

int getL(int i, int l, int r, int lq, int rq) {
    if (lq >= r || l >= rq || lef[i] >= lq) return -1;
    if (r - l == 1) return l;
    int m = (r + l) / 2;
    int res = getL(2 * i + 1, l, m, lq, rq);
    if (res == -1) res = getL(2 * i + 2, m, r, lq, rq);
    return res;
}

void func1(int c, int u, int v, int to) {
    auto it = in[c].lower_bound(u);
    vector < int > del;
    int lst = -1;
    if (it != in[c].begin()) {
        it--;
        lst = *it;
        it++;
    }
    while (it != in[c].end()) {
        int now = *it;
        if (now >= v) break;
        in[to].insert(now);
        upd(to, 1);
        upd(c, -1);
        cmp[now] = to;
        it++;
        del.push_back(now);
    }
    for (auto key : del) in[c].erase(key);
    nxtR[del.back()] = del.back();
    nxtL[del[0]] = del[0];
    update(0, 1, n, del[0]);
    update(0, 1, n, del.back());
    if (lst != -1) {
        if (it == in[c].end()) nxtR[lst] = lst;
        else nxtR[lst] = *it;
        update(0, 1, n, lst);
    }
    if (it != in[c].end()) {
        if (lst == -1) {
            nxtL[*it] = *it;
        } else {
            nxtL[*it] = lst;
        }
        update(0, 1, n, *it);
    }
}

void func2(int c, int u, int v, int to) {
    auto it = in[c].begin();
    vector < int > del;
    while (it != in[c].end()) {
        int now = *it;
        if (now >= u) break;
        in[to].insert(now);
        cmp[now] = to;
        upd(to, 1);
        upd(c, -1);
        del.push_back(now);
        it++;
    }
    if (it != in[c].end()) {
        nxtL[*it] = *it;
        update(0, 1, n, *it);
    }
    it = in[c].lower_bound(v);
    assert(it != in[c].begin());
    it--;
    int tmp = *it;
    assert(tmp >= u);
    nxtR[tmp] = tmp;
    update(0, 1, n, tmp);
    it++;
    if (!del.empty()) {
        if (it == in[c].end()) {
            nxtR[del.back()] = del.back();
        } else {
            nxtR[del.back()] = *it;
        }
        update(0, 1, n, del.back());
    }
    if (it != in[c].end()) {
        if (!del.empty()) nxtL[*it] = del.back();
        else nxtL[*it] = *it;
        update(0, 1, n, *it);
    }
    while (it != in[c].end()) {
        int now = *it;
        in[to].insert(now);
        cmp[now] = to;
        upd(to, 1);
        upd(c, -1);
        del.push_back(now);
        it++;
    }
    for (auto key : del) in[c].erase(key);
}

main() {
#ifdef HOME
    freopen("input.txt", "r", stdin);
#endif // HOME
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int m, u, v, cur = 2;
        cin >> n >> m;
        for (int j = 0; j < 3; j++) b[j] = {};
        for (int i = 1; i <= n; i++) sz[i] = 0, in[i] = {};
        for (int i = 1; i < n; i++) b[0].insert(i), nxtL[i] = max(1, i - 1), nxtR[i] = min(i + 1, n - 1), cmp[i] = 1, sz[1]++, in[1].insert(i);
        add = sz[1] * (sz[1] - 1) / 2;
        if (n > 1) build(0, 1, n);
        for (int M = 1; M <= m; M++) {
            cin >> u >> v;
            if (u > v) swap(u, v);

            for (int j = 1; j >= 0; j--) {
                auto it = b[j].lower_bound(u);
                vector < int > del;
                while (it != b[j].end() && *it < v) {
                    del.push_back(*it);
                    it++;
                }
                for (auto key : del) {
                    b[j].erase(key);
                    b[j + 1].insert(key);
                }

                while (n > 1 && u < v) {
                    int pos = getR(0, 1, n, u, v);
                    if (pos == -1) break;
                    int L = in[cmp[pos]].order_of_key(u), R = in[cmp[pos]].order_of_key(v);
                    if (R - L <= sz[cmp[pos]] / 2) {
                        func1(cmp[pos], u, v, cur);
                    } else {
                        func2(cmp[pos], u, v, cur);
                    }
                    cur++;
                }

                while (n > 1 && u < v) {
                    int pos = getL(0, 1, n, u, v);
                    if (pos == -1) break;
                    int L = in[cmp[pos]].order_of_key(u), R = in[cmp[pos]].order_of_key(v);
                    if (R - L <= sz[cmp[pos]] / 2) {
                        func1(cmp[pos], u, v, cur);
                    } else {
                        func2(cmp[pos], u, v, cur);
                    }
                    cur++;
                }
            }

            ll ans = 0, cnt = b[0].size();
            ans += (ll)M * cnt;
            ans += b[1].size();
            ans += cnt * (n - 2);
            ans -= cnt * (cnt - 1);
            ans += add;

            for (int i = 1; i < n; i++) {
                int pos = i;
                for (int j = 1; j < i; j++) {
                    if (cmp[i] == cmp[j]) pos = j;
                }
                assert(pos == nxtL[i]);
                pos = i;
                for (int j = i + 1; j < n; j++) {
                    if (cmp[i] == cmp[j]) {
                        pos = j;
                        break;
                    }
                }
                assert(pos == nxtR[i]);

                int sum = 0;
                for (int j = 1; j < n; j++) if (cmp[j] == cmp[i]) sum++;
                assert(sum == sz[cmp[i]]);
            }


            cout << ans << '\n';
        }
    }
    return 0;
}