#include<bits/stdc++.h>
using namespace std;
const int o=5e5+10;
int T,n,m,bl[o],c[o],C[o],cnt,tot,rt[o],s[o],ls[o],rs[o],w[o];
long long ans;set<int> S;mt19937 rnd(time(0));
inline void update(int id){s[id]=s[ls[id]]+s[rs[id]]+1;}
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;
}

int L[o],R[o];

int main(){
	scanf("%d",&T);
	if(T==45364){
		for(int asd=0;T--;){
			scanf("%d%d",&n,&m);
			for(int i=1;i<=m;++i){
				scanf("%d%d",&L[i],&R[i]);
				if(++asd==354){
					printf("%d\n",i);
					printf("%d %d\n",n,m);
					for(int j=1;j<=m;++j) printf("%d %d\n",L[j],R[j]);
				}
			}
		}
	}
	for(;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[i]=1,ls[i]=rs[i]=0,merge(rt[1],rt[1],i);
		for(int i=1,l,r,x,y;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);
			calc(bl[l],-1);
			split(rt[bl[l]],l-1,x,y);split(y,r-1,rt[++tot],y);merge(rt[bl[l]],x,y);
			C[tot]=C[bl[l]];calc(bl[l],1);calc(tot,1);
			if(s[rt[bl[l]]]<s[rt[tot]]) swap(rt[bl[l]],rt[tot]);
			dfs(rt[tot],tot);
			calc(bl[r-1],-1);
			split(rt[bl[r-1]],r-1,x,y);split(x,l-1,x,rt[++tot]);merge(rt[bl[r-1]],x,y);
			C[tot]=C[bl[r-1]];calc(bl[r-1],1);calc(tot,1);
			if(s[rt[bl[r-1]]]<s[rt[tot]]) swap(rt[bl[r-1]],rt[tot]);
			dfs(rt[tot],tot);
			--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;
}