#include<bits/stdc++.h>
#define LL long long
#define DB double
#define MOD 1000000007
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define lowbit(x) ((-x) & x)
#define MP make_pair
#define MT make_tuple
#define VI vector<int>
#define VL vector<LL>
#define VII VI::iterator
#define VLI VL::iterator
#define all(x) x.begin(), x.end()
#define EB emplace_back
#define PII pair<int, int>
#define SI set<int>
#define SII SI::iterator
#define fi first
#define se second
using namespace std;
template<typename T> void chkmn(T &a, const T b) { (a > b) && (a = b); }
template<typename T> void chkmx(T &a, const T b) { (a < b) && (a = b); }
void Inc(int &a, const int &b) { ((a += b) >= MOD) && (a -= MOD); }
void Dec(int &a, const int &b) { ((a -= b) < 0) && (a += MOD); }
void Mul(int &a, const int &b) { a = 1LL * a * b % MOD; }
void Sqr(int &a) { a = 1LL * a * a % MOD; }
int inc(const int &a, const int &b) { return (a + b >= MOD) ? a + b - MOD : a + b; }
int dec(const int &a, const int &b) { return (a - b < 0) ? a - b + MOD : a - b; }
int mul(const int &a, const int &b) { return 1LL * a * b % MOD; }
int sqr(const int &a) { return 1LL * a * a % MOD; }
int qwqmi(int x, int k = MOD - 2)
{
	int res = 1;
	while(k)
	{
		if(k & 1) Mul(res, x);
		k >>= 1, Sqr(x);
	}
	return res;
}
void read(int &x)
{
	x = 0;
	int f = 1;
	char ch = getchar();
	while(!isdigit(ch))
	{
		if(ch == '-')
			f = -1;
		ch = getchar();
	}
	while(isdigit(ch))
	{
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	x = x * f;
}
const int N = 1e6 + 5;
int T, n, m, ecnt;
namespace Brute3 // n <= 2000
{
	const int base = 1145141;
	int hsh[2005], cnt[2005];
	map<int, int> mp;
	void clear()
	{
		mp.clear();
		memset(hsh, 0, sizeof(hsh));
		memset(cnt, 0, sizeof(cnt));
	}
	void update(int l, int r)
	{
		for(int i = l; i <= r; ++i)
		{
			++cnt[i];
			hsh[i] = inc(mul(hsh[i], base), ecnt);
		}
	}
	int calc()
	{
		int res = 0;
		int zcnt = 0, ocnt = 0;
		mp.clear();
		for(int i = 1; i < n; ++i)
		{
			zcnt += (cnt[i] == 0);
			ocnt += (cnt[i] == 1);
			if(cnt[i] > 0) mp[hsh[i]]++;
		}
		res += zcnt * (ecnt - 1) - zcnt * (zcnt - 1) / 2;
		res += ocnt;
		for(auto now : mp)
		{
			int c = now.se;
			res += c * (c - 1) / 2;
		}
		return res;
	}
	void work()
	{
		clear();
		for(int cas = 1; cas <= m; ++cas)
		{
			++ecnt;
			int l, r;
			read(l), read(r);
			if(l > r) swap(l, r);
			if(l < r) update(l, r - 1);
			printf("%d\n", calc());
		}
	}
};
namespace Cleveland // special
{
	LL W = 0, zcnt, ocnt;
	LL calc()
	{
		LL res = W;
		res += zcnt * (ecnt - 1) - zcnt * (zcnt - 1) / 2;
		res += ocnt;
		return res;
	}
	void clear()
	{
		W = 0;
		zcnt = n - 1;
		ocnt = 0;
	}
	void work()
	{
		clear();
		for(int cas = 1; cas <= m; ++cas)
		{
			++ecnt;
			int l, r;
			read(l), read(r);
			int len = r - l;
			zcnt -= len;
			ocnt += len;
			W += 1LL * len * (len - 1);
			printf("%lld\n", calc());
		}
	}	
};
namespace Enterprise // std
{
	int bel[N], pre[N], nxt[N];
	int lcnt, hd[N], sz[N];
	struct Akashi // cut
	{
		int id, pos, op; // op = 1:l / 2:r
		friend bool operator < (Akashi A, Akashi B)
		{
			if(A.id != B.id) return A.id < B.id;
			if(A.op != B.op) return A.op < B.op;
			return A.pos < B.pos;
		}
	};
	void Print_Chain()
	{
		printf("lcnt : %d\n", lcnt);
		for(int i = 1; i <= lcnt; ++i)
		{
			printf("%d : ", sz[i]);
			int x = hd[i];
			while(1)
			{
				printf("%d ", x);
				if(x == nxt[x]) break;
				x = nxt[x];
			}
			puts("");
		}
	}
	vector<PII> vec;
	LL W = 0;
	LL func(int x)
	{
		return 1LL * x * (x - 1) / 2;
	}
	struct SGT
	{
		struct SegTree
		{
			int l, r;
			int cnt[2];
			int mnv, mxv;
			int add;
		}tr[N << 2];	
		void pushup(int p)
		{
			tr[p].cnt[0] = tr[ls(p)].cnt[0] + tr[rs(p)].cnt[0];
			tr[p].cnt[1] = tr[ls(p)].cnt[1] + tr[rs(p)].cnt[1];
			tr[p].mnv = min(tr[ls(p)].mnv, tr[rs(p)].mnv);
			tr[p].mxv = max(tr[ls(p)].mxv, tr[rs(p)].mxv);
		}
		void build(int p, int l, int r)
		{
			tr[p].l = l;
			tr[p].r = r;
			tr[p].add = 0;
			if(l == r)
			{
				tr[p].cnt[0] = 1;
				tr[p].cnt[1] = 0;
				tr[p].mnv = pre[l];
				tr[p].mxv = nxt[l];
				return;
			}
			int mid = l + (r - l) / 2;
			build(ls(p), l, mid);
			build(rs(p), mid + 1, r);
			pushup(p);
		}
		void cal(SegTree &u, int v)
		{
			u.add += v;
			u.cnt[1] = 0;
			if(v == 1) 
				u.cnt[1] = u.cnt[0];
			u.cnt[0] = 0;
		}
		void pushdown(int p)
		{
			if(tr[p].add)
			{
				cal(tr[ls(p)], tr[p].add);
				cal(tr[rs(p)], tr[p].add);
				tr[p].add = 0;
			}
		}
		void modify_add(int p, int l, int r, int v)
		{
			if(tr[p].l >= l && tr[p].r <= r)
			{
				cal(tr[p], v);
				return;
			}
			pushdown(p);
			int mid = tr[p].l + (tr[p].r - tr[p].l) / 2;
			if(mid >= l) modify_add(ls(p), l, r, v);
			if(mid < r) modify_add(rs(p), l, r, v);
			pushup(p);
		}
		void find_L(int p, int l, int r)
		{
			if(tr[p].l > r || tr[p].r < l || tr[p].mnv >= l) return;
			if(tr[p].l == tr[p].r) return vec.EB(MP(bel[tr[p].l], tr[p].l)), void();
			if(tr[ls(p)].mnv < l) find_L(ls(p), l, r);
			if(tr[rs(p)].mnv < l) find_L(rs(p), l, r);
		}
		void find_R(int p, int l, int r)
		{
			if(tr[p].l > r || tr[p].r < l || tr[p].mxv <= r) return;
			if(tr[p].l == tr[p].r) return vec.EB(MP(bel[tr[p].l], nxt[tr[p].l])), void();
			if(tr[ls(p)].mxv > r) find_R(ls(p), l, r);
			if(tr[rs(p)].mxv > r) find_R(rs(p), l, r);
		}
		void modify_mnx(int p, int x, int v, int op) 
		{
			if(tr[p].l == tr[p].r)
			{
				if(op == 0) tr[p].mnv = v;
				else tr[p].mxv = v;
				return;
			}
			pushdown(p);
			int mid = tr[p].l + (tr[p].r - tr[p].l) / 2;
			if(mid >= x) modify_mnx(ls(p), x, v, op);
			else modify_mnx(rs(p), x, v, op);
			pushup(p);
		}
	}T;
	void disconnect(int x) // pre[x] <-/-> x
	{
		int y = pre[x];
		pre[x] = x; T.modify_mnx(1, x, x, 0);
		nxt[y] = y; T.modify_mnx(1, y, y, 1);
	}
	void connect(int x, int y) // x <---> y
	{
		pre[y] = x; T.modify_mnx(1, y, x, 0);
		nxt[x] = y; T.modify_mnx(1, x, y, 1);
	}
	void Make_New_Chain(vector<int> V)
	{
		++lcnt;
		hd[lcnt] = V[0];
		sz[lcnt] = (int)V.size();
		for(int i = 0; i < (int)V.size(); ++i)
		{
			int x = V[i];
			bel[x] = lcnt;
			if(i > 0) connect(V[i - 1], x);
		}
	}
	void cut(int id, int l, int r) // [L, p) [l, r] (q, R]
	{
//		puts("3-cut");
		W -= func(sz[id]);
		int p = pre[l], q = nxt[r];
		disconnect(l);
		disconnect(q);
		connect(p, q);
//		printf("### %d %d %d\n", l, r, nxt[3]);
		vector<int> V1, V2;
		V1.clear(), V2.clear();
		int u = hd[id], v = l;
		while(1)
		{
			V1.EB(u), V2.EB(v);
			if(nxt[u] == u && u != p)
			{
				hd[id] = l;
				sz[id] -= (int)V1.size();
				Make_New_Chain(V1);
				break;
			}
			else if(nxt[v] == v)
			{
				sz[id] -= (int)V2.size();
				Make_New_Chain(V2);
				break;
			}
			u = (u == p) ? q : nxt[u];
			v = nxt[v];
		}
		W += func(sz[id]) + func(sz[lcnt]);
	}
	void cut(int id, int r) // [L, p) [r, R]
	{
//		puts("2-cut");
		W -= func(sz[id]);
		disconnect(r);
		vector<int> V1, V2;
		V1.clear(), V2.clear();
		int u = hd[id], v = r;
		while(1)
		{
			V1.EB(u), V2.EB(v);
			if(nxt[u] == u)
			{
				hd[id] = r;
				sz[id] -= (int)V1.size();
				Make_New_Chain(V1);
				break;
			}
			else if(nxt[v] == v)
			{
				sz[id] -= (int)V2.size();
				Make_New_Chain(V2);
				break;
			}
			u = nxt[u];
			v = nxt[v];
		}
		W += func(sz[id]) + func(sz[lcnt]);
	}
	LL calc()
	{
		LL res = 0;
		int zcnt = T.tr[1].cnt[0];
		int ocnt = T.tr[1].cnt[1];
		res += 1LL * zcnt * (ecnt - 1) - func(zcnt); // case1
		res += ocnt; // case2
		res += W - func(zcnt); // case3
		return res;
	}
	void clear()
	{
		W = 1LL * (n - 1) * (n - 2) / 2;
		lcnt = 1;
		hd[lcnt] = 1;
		sz[lcnt] = n - 1;
		for(int i = 1; i <= n - 1; ++i)
		{
			bel[i] = 1;
			pre[i] = max(1, i - 1);
			nxt[i] = min(n - 1, i + 1);
		}
		T.build(1, 1, n - 1);
	}
	void work()
	{
		clear();
		for(int cas = 1; cas <= m; ++cas)
		{
			++ecnt;
			vec.clear();
			int l, r; read(l), read(r);
			if(l > r) swap(l, r);
			if(l == r) 
			{
				printf("%lld\n", calc());
				continue;
			}
			--r;
			T.modify_add(1, l, r, 1);
			T.find_L(1, l, r);
			T.find_R(1, l, r);
			sort(vec.begin(), vec.end());
			for(int i = 0; i < (int)vec.size();)
			{
				if(i + 1 < (int)vec.size() && vec[i].fi == vec[i + 1].fi)
					cut(vec[i].fi, vec[i].se, pre[vec[i + 1].se]), i += 2;
				else cut(vec[i].fi, vec[i].se), ++i;
			}
			printf("%lld\n", calc());
			
//			Print_Chain();
		}
	}	
};
void work()
{
	read(n), read(m);
	ecnt = n - 1;
//	if(n <= 2000 && m <= 2000) 
//		Brute3::work();
//	else assert(0);
	Enterprise::work();
}
int main()
{
	scanf("%d", &T);
	while(T--)
		work();
	return 0;
}

/*
3
4 3
2 4
4 2
3 3
7 3
3 4
1 2
1 7
6 4
1 3
4 6
2 5
3 4
*/