#include<bits/stdc++.h>
using namespace std;
const int o=1e6+10;
int T,n,m,bl[o],c[o],C[o],cnt,tot,rt[o],s[o],ls[o],rs[o],w[o],l_[o],r_[o];long long ans;
pair<int,int> pre[o],suf[o],pr;set<int> S;mt19937 rnd(time(0));
inline void update(int id){
	s[l_[id]=r_[id]=id]=1;
	if(ls[id]) s[id]+=s[ls[id]],l_[id]=l_[ls[id]];
	if(rs[id]) s[id]+=s[rs[id]],r_[id]=r_[rs[id]];
}
void merge(int&id,int x,int y){
	if(!x||!y){id=x|y;return;}
	if(w[x]<w[y]) id=x,merge(rs[id],rs[x],y);
	else id=y,merge(ls[id],x,ls[y]);
	update(id);
}
void split(int id,int val,int&x,int&y){
	if(!id){x=y=0;return;}
	if(id<=val) x=id,split(rs[id],val,rs[x],y);
	else y=id,split(ls[id],val,x,ls[y]);
	update(id);
}
void dfs(int id,int val){if(id) bl[id]=val,dfs(ls[id],val),dfs(rs[id],val);}
inline void calc(int x,int coef){
	if(!C[x]){cnt+=coef*s[rt[x]];return;}
	if(C[x]==1) ans+=coef*s[rt[x]]*(s[rt[x]]+1ll)/2;
	else ans+=coef*s[rt[x]]*(s[rt[x]]-1ll)/2;
}
inline void Update(int id){pre[id]=min(pre[id<<1],pre[(id<<1)|1]);suf[id]=max(suf[id<<1],suf[(id<<1)|1]);}
void build(int id,int l,int r){
	if(l==r){pre[id]=make_pair((l>1)?l-1:o,l);suf[id]=make_pair((r<n-1)?r+1:0,r);return;}
	int md=l+r>>1;
	build(id<<1,l,md);build((id<<1)|1,md+1,r);
	Update(id);
}
void modify1(int id,int pos,int val,int l=1,int r=n-1){
	if(l==r){pre[id].first=val;return;}
	int md=l+r>>1;
	if(pos<=md) modify1(id<<1,pos,val,l,md);
	else modify1((id<<1)|1,pos,val,md+1,r);
	Update(id);
}
void modify2(int id,int pos,int val,int l=1,int r=n-1){
	if(l==r){suf[id].first=val;return;}
	int md=l+r>>1;
	if(pos<=md) modify2(id<<1,pos,val,l,md);
	else modify2((id<<1)|1,pos,val,md+1,r);
	Update(id);
}
pair<int,int> query1(int id,int ql,int qr,int l=1,int r=n-1){
	if(ql<=l&&r<=qr) return pre[id];
	int md=l+r>>1;
	if(qr<=md) return query1(id<<1,ql,qr,l,md);
	if(md<ql) return query1((id<<1)|1,ql,qr,md+1,r);
	return min(query1(id<<1,ql,qr,l,md),query1((id<<1)|1,ql,qr,md+1,r));
}
pair<int,int> query2(int id,int ql,int qr,int l=1,int r=n-1){
	if(ql<=l&&r<=qr) return suf[id];
	int md=l+r>>1;
	if(qr<=md) return query2(id<<1,ql,qr,l,md);
	if(md<ql) return query2((id<<1)|1,ql,qr,md+1,r);
	return max(query2(id<<1,ql,qr,l,md),query2((id<<1)|1,ql,qr,md+1,r));
}
inline void upd(int t,int l,int r){
	int x,y;
	calc(t,-1);
	split(rt[t],l-1,x,y);split(y,r-1,rt[++tot],y);
	if(x&&y) modify1(1,l_[y],r_[x]),modify2(1,r_[x],l_[y]);
	if(x&&!y) modify2(1,r_[x],0);
	if(y&&!x) modify1(1,l_[y],o);
	if(rt[tot]) modify1(1,l_[rt[tot]],o),modify2(1,r_[rt[tot]],0);
	merge(rt[t],x,y);
	C[tot]=C[t];calc(t,1);calc(tot,1);
	if(s[rt[t]]<s[rt[tot]]) swap(rt[t],rt[tot]);
	dfs(rt[tot],tot);
}
int main(){
	for(scanf("%d",&T);T--;S.clear(),ans=0){
		scanf("%d%d",&n,&m);cnt=n-1;tot=1;
		for(int i=1;i<n;++i)
			S.insert(i),c[i]=0,bl[i]=1,w[i]=rnd(),s[l_[i]=r_[i]=i]=1,ls[i]=rs[i]=0,merge(rt[1],rt[1],i);
		if(n>1) build(1,1,n-1);
		for(int i=1,l,r;i<=m;printf("%lld\n",ans+cnt*(cnt-1ll)/2+cnt*(n+i-1ll-cnt)),++i){
			scanf("%d%d",&l,&r);
			if(l==r) continue;
			if(l>r) swap(l,r);
			for(;(pr=query1(1,l,r-1)).first<l;upd(bl[pr.second],l,r));
			for(;(pr=query2(1,l,r-1)).first>=r;upd(bl[pr.second],l,r));
			--l;
			for(set<int>::iterator iter;(iter=S.upper_bound(l))!=S.end()&&(*iter)<r;){
				calc(bl[l=*iter],-1);C[bl[l]]=++c[l];calc(bl[l],1);
				if(c[l]==2) S.erase(l);
			}
		}
		for(int i=1;i<=tot;++i) rt[i]=C[i]=0;
	}
	return 0;
}