#include <bits/stdc++.h>
using namespace std;
const int MAXN = 800005;
const int the_answer_to_life_the_universe_and_everything = 42;
int T, n, m;
int pre[MAXN], nxt[MAXN], siz[MAXN], root[MAXN], bl[MAXN], tot;
long long cnt;
struct SegmentTree {
    struct Node {
        int mn, mx;
        int cnt[2], tag;
    } t[MAXN << 2];
#define lc (i << 1)
#define rc (i << 1 | 1)
    void tag(int i, int v) {
        if (v == 1) {
            t[i].cnt[1] = t[i].cnt[0], t[i].cnt[0] = 0;
        } else {
            t[i].cnt[0] = t[i].cnt[1] = 0;
        }
        t[i].tag += v;
    }
    void pushDown(int i) {
        if (t[i].tag) {
            tag(lc, t[i].tag);
            tag(rc, t[i].tag);
            t[i].tag = 0;
        }
    }
    void pushUp(int i) {
        t[i].mn = min(t[lc].mn, t[rc].mn);
        t[i].mx = max(t[lc].mx, t[rc].mx);
        t[i].cnt[0] = t[lc].cnt[0] + t[rc].cnt[0];
        t[i].cnt[1] = t[lc].cnt[1] + t[rc].cnt[1];
    }
    void build(int i = 1, int l = 1, int r = n - 1) {
        t[i].tag = 0;
        if (l == r) {
            t[i].cnt[0] = 1, t[i].cnt[1] = 0;
            t[i].mn = pre[l], t[i].mx = nxt[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(lc, l, mid);
        build(rc, mid + 1, r);
        pushUp(i);
    }
    void add(int a, int b, int i = 1, int l = 1, int r = n - 1) {
        if (a <= l && r <= b) {
            tag(i, 1);
            return;
        }
        pushDown(i);
        int mid = (l + r) >> 1;
        if (a <= mid) add(a, b, lc, l, mid);
        if (b > mid) add(a, b, rc, mid + 1, r);
        pushUp(i);
        // printf("%d [%d, %d] %d %d\n", i, l, r, t[i].cnt[0], t[i].cnt[1]);
    }
    void findL(int a, int b, int v, vector<pair<int, int>> &p, int i = 1, int l = 1, int r = n - 1) {
        if (t[i].mn >= v) return;
        if (l == r) {
            p.push_back({ bl[l], l });
            return;
        }
        int mid = (l + r) >> 1;
        if (a <= mid) findL(a, b, v, p, lc, l, mid);
        if (b > mid) findL(a, b, v, p, rc, mid + 1, r);
    }
    void findR(int a, int b, int v, vector<pair<int, int>> &p, int i = 1, int l = 1, int r = n - 1) {
        if (t[i].mx <= v) return;
        if (l == r) {
            p.push_back({ bl[nxt[l]], nxt[l] });
            return;
        }
        int mid = (l + r) >> 1;
        if (a <= mid) findR(a, b, v, p, lc, l, mid);
        if (b > mid) findR(a, b, v, p, rc, mid + 1, r);
    }
    void setPre(int d, int v, int i = 1, int l = 1, int r = n - 1) {
        if (l == r) {
            pre[l] = t[i].mn = v;
            return;
        }
        pushDown(i);
        int mid = (l + r) >> 1;
        if (d <= mid) setPre(d, v, lc, l, mid);
        else setPre(d, v, rc, mid + 1, r);
        pushUp(i);
    }
    void setNxt(int d, int v, int i = 1, int l = 1, int r = n - 1) {
        if (l == r) {
            nxt[l] = t[i].mx = v;
            return;
        }
        pushDown(i);
        int mid = (l + r) >> 1;
        if (d <= mid) setNxt(d, v, lc, l, mid);
        else setNxt(d, v, rc, mid + 1, r);
        pushUp(i);
    }
} st;
long long calcAns(int m) {
    long long ans = 0;
    int zero = st.t[1].cnt[0], one = st.t[1].cnt[1];
    // printf("zero = %d\n", zero);
    // case 1: zero - m and zero - nonzero
    ans += 1ll * zero * (n - 1 + m - zero);
    // printf("case 1: %lld\n", 1ll * zero * (n - 1 + m - zero));
    // case 2: one - m
    ans += one;
    // printf("case 2: %lld\n", one);
    // case 3: nonzero - nonzero
    ans += cnt;
    // printf("case 3: %lld\n", cnt);
    return ans;
}
void connect(int x, int y) {
    st.setPre(y, x);
    // printf("pre[%d]=%d\n", y, x);
    st.setNxt(x, y);
    // printf("nxt[%d]=%d\n", x, nxt[x]);
}
void disconnect(int x) {
    int y = pre[x];
    st.setPre(x, x);
    // printf("pre[%d]=%d\n", x, x);
    st.setNxt(y, y);
    // printf("nxt[%d]=%d\n", y, y);
}
void newList(vector<int> &a) {
    ++tot;
    root[tot] = a[0];
    siz[tot] = a.size();
    for (int i : a) bl[i] = tot;
}
long long C(int x) {
    return 1ll * x * (x - 1) / 2;
}
void cut(int p, int l) {
    // printf("cut %d %d\n", p, l);
    cnt -= C(siz[p]);
    vector<int> v1, v2;
    int p1 = root[p], p2 = l;
    while (the_answer_to_life_the_universe_and_everything == 42) {
        v1.push_back(p1), v2.push_back(p2);
        int np1 = nxt[p1] == l ? p1 : nxt[p1];
        int np2 = nxt[p2];
        // printf("%d -> %d\n", p1, np1);
        // printf("%d -> %d\n", p2, np2);
        if (np1 == p1) {
            newList(v1);
            root[p] = l;
            siz[p] -= v1.size();
            break;
        } else if (np2 == p2) {
            newList(v2);
            siz[p] -= v2.size();
            break;
        } else {
            p1 = np1;
            p2 = np2;
        }
    }
    // printf("cut %d to [%d, %d]\n", p, siz[tot], siz[p]);
    disconnect(l);
    cnt += C(siz[tot]) + C(siz[p]);
}
void cut(int p, int l, int r) {
    // printf("cut %d [%d, %d]\n", p, l, r);
    cnt -= C(siz[p]);
    vector<int> v1, v2;
    int p1 = root[p], p2 = l;
    while (the_answer_to_life_the_universe_and_everything == 42) {
        v1.push_back(p1), v2.push_back(p2);
        int np1 = nxt[p1] == l ? r : nxt[p1];
        int np2 = nxt[p2] == r ? p2 : nxt[p2];
        if (np1 == p1) {
            newList(v1);
            root[p] = l;
            siz[p] -= v1.size();
            break;
        } else if (np2 == p2) {
            newList(v2);
            siz[p] -= v2.size();
            break;
        } else {
            p1 = np1;
            p2 = np2;
        }
    }
    int tmp = pre[l];
    disconnect(l), disconnect(r), connect(tmp, r);
    // printf("cut %d to [%d, %d]\n", p, siz[tot], siz[p]);
    cnt += C(siz[tot]) + C(siz[p]);
}
int main() {
    freopen("L.in", "r", stdin);
    scanf("%d", &T);
    while (T--) {
        if (T == 45540 - 10) {
            return 0;
        }
        scanf("%d%d", &n, &m);
        if (n == 1) {
            for (int i = 1; i <= m; i++) {
                scanf("%*d%*d");
                printf("0\n");
            }
            continue;
        }
        tot = 1;
        cnt = C(n - 1);
        root[1] = 1;
        nxt[n - 1] = n - 1, pre[1] = 1;
        siz[1] = n - 1;
        for (int i = 1; i <= n - 1; i++) {
            bl[i] = 1;
        }
        for (int i = 1; i < n - 1; i++) {
            nxt[i] = i + 1, pre[i + 1] = i;
        }
        st.build();
        for (int i = 1; i <= m; i++) {
            int u, v; scanf("%d%d", &u, &v);
            if (u == v) {
                printf("%lld\n", calcAns(i));
                continue;
            }
            if (u > v) swap(u, v);
            v--;
            st.add(u, v);
            vector<pair<int, int>> pt;
            st.findL(u, v, u, pt);
            st.findR(u, v, v, pt);
            sort(pt.begin(), pt.end());
            // for (auto p : pt) {
            //     printf("(%d, %d) ", p.first, p.second);
            // }
            // printf("\n");
            for (int i = 0; i < pt.size(); i++) {
                if (i + 1 < pt.size() && pt[i].first == pt[i + 1].first) {
                    cut(pt[i].first, pt[i].second, pt[i + 1].second);
                    i++;
                } else {
                    cut(pt[i].first, pt[i].second);
                }
            }
            printf("%lld\n", calcAns(i));
        }
        // printf("\n");
    }
    return 0;
}
/*
15
12
3
2
*/