#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MP make_pair
mt19937 rnd(time(0));
const int MAXN=2.5e5+5;
int n,m,fa[MAXN],siz[MAXN],pre[MAXN],suf[MAXN];
ll ans[MAXN];
vector<pair<int,int> > vec[MAXN];
inline int find(int x){
	while(x^fa[x]) x=fa[x]=fa[fa[x]];
	return x;
}
struct segt{
int minn[MAXN<<2],maxx[MAXN<<2];
void init(){for(int i=0;i<=4*n;i++)minn[i]=maxx[i]=0;} 
void pushup(int id){
	minn[id]=min(minn[id<<1],minn[id<<1|1]);
	maxx[id]=max(maxx[id<<1],maxx[id<<1|1]);
}
int askL(int L,int R,int x,int id=1,int l=1,int r=n){
	int mid=l+r>>1;
	if(L<=l&&r<=R){
		if(minn[id]>x) return 0;
		else if(l==r) return l;
		else if(minn[id<<1]<=x?askL(L,R,x,id<<1,l,mid):askL(L,R,x,id<<1|1,mid+1,r));
	} 
	int ans=0;
	if(L<=mid&&(ans=askL(L,R,x,id<<1,l,mid))) return ans;
	if(mid<R&&(ans=askL(L,R,x,id<<1|1,mid+1,r))) return ans;
	return 0;
}
int askR(int L,int R,int x,int id=1,int l=1,int r=n){
	int mid=l+r>>1;
	if(L<=l&&r<=R){
		if(maxx[id]<x) return 0;
		else if(l==r) return l;
		else return (maxx[id<<1|1]>=x?askR(L,R,x,id<<1|1,mid+1,r):askR(L,R,x,id<<1,l,mid));
	}
	int ans=0;
	if(mid<R&&(ans=askR(L,R,x,id<<1|1,mid+1,r))) return ans;
	if(L<=mid&&(ans=askR(L,R,x,id<<1,l,mid))) return ans;
	return 0;
}
void update(int x,int v,int id=1,int l=1,int r=n){
	if(l==r){minn[id]=maxx[id]=v;return;}
	int mid=l+r>>1;
	if(x<=mid) update(x,v,id<<1,l,mid);
	else update(x,v,id<<1|1,mid+1,r);
	pushup(id); 
}
}Tp,Ts,Tc;
struct BIT{
ll a[MAXN];
void init(){for(int i=0;i<=n;i++)a[i]=0;} 
void add(int x,ll d){while(x<=n){a[x]+=d;x+=(x&-x);}}
ll ask(int x){ll r=0;while(x){r+=a[x];x-=(x&-x);}return r;} 
}T,B;
void solve(){
	cin>>n>>m;n--; 
	Tp.init(),Ts.init(),Tc.init();T.init();B.init();
	for(int i=1;i<=n;i++) pre[i]=i-1,suf[i]=i+1;
	pre[1]=1e9,suf[n]=-1e9;
	for(int i=1;i<=n;i++) Tp.update(i,pre[i]),Ts.update(i,suf[i]); 
	int c0=n,c1=0;
	for(int i=1;i<=m;i++){
		vec[i].clear();
		int l,r,x,v=rnd();cin>>l>>r;
		if(l==r){
			ans[i]=c0*(n+i-c0)+c1;
			continue;
		} 
		if(l>r)swap(l,r); r--;
		x=l-1;
		B.add(l,1);B.add(r+1,-1);
		T.add(l,v);T.add(r+1,-v); 
		map<ll,pair<int,int> > rep;
		while(x<r&&(x=Tc.askL(x+1,r,1))){
			if(B.ask(x)==2) c1--; 
			if(B.ask(x)==1) c0--,c1++;
			Tc.update(x,B.ask(x));
		}
		x=0;ans[i]=c0*(n+i-c0)+c1;
//		cout<<ans[i]<<endl;
		while(x=Tp.askL(l,r,l-1)) rep[T.ask(x)].first=x,Tp.update(x,1e9);
		while(x=Ts.askR(l,r,r+1)) rep[T.ask(x)].second=x,Ts.update(x,-1e9); 
		for(auto j:rep){
			int x=j.second.first,y=j.second.second;
			if(x&&y){
				vec[i].push_back(MP(pre[x],x));
				Ts.update(pre[x],suf[y]);
				suf[pre[x]]=suf[y];
				Tp.update(suf[y],pre[x]);
				pre[suf[y]]=pre[x];
				Tp.update(x,1e9);Ts.update(y,-1e9);
				pre[x]=1e9;suf[y]=-1e9;
			}else if(x){
				vec[i].push_back(MP(pre[x],x));
				Ts.update(pre[x],-1e9);
				suf[pre[x]]=-1e9;
				Tp.update(x,1e9);
				pre[x]=1e9;
			}else{
				vec[i].push_back(MP(y,suf[y]));
				Tp.update(suf[y],1e9);
				pre[suf[y]]=1e9;
				Ts.update(y,-1e9);
				suf[y]=-1e9;
			}
		}
//		cout<<"AFTER "<<i<<endl;
//		for(int i=1;i<=n;i++) cout<<pre[i]<<' '<<suf[i]<<endl;
	}
	ll sum=0;
	auto merge=[&](int x,int y){
		x=find(x);y=find(y);
		sum+=siz[x]*siz[y];
		siz[x]+=siz[y];fa[y]=x;
	};
	for(int i=1;i<=n;i++) siz[i]=1,fa[i]=i;
	for(int i=1;i<=n;i++) if(suf[i]>0) merge(i,suf[i]);
	for(int i=m;i>=1;i--){
		ans[i]+=sum;
		for(auto j:vec[i]) merge(j.first,j.second);
	} 
	for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
}
int main(){
	ios::sync_with_stdio(false);
	int _;cin>>_;
	while(_--) solve();
}