#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
	int s=0,w=1;char ch;
	while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
inline ll lread()
{
	ll s=0,w=1;char ch;
	while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
int mi[1000001];
int ma[1000001];
int bel[250005];//每一个点对应的链表编号
int root[250005];//链表的链头
int cnt[250005];//链表内元素个数
int nx[250005];
int lt[200005];
set<int>S0,S1;
int n,m,c;
ll ans;
inline void push_up(int p)
{
	mi[p]=min(mi[p*2],mi[p*2|1]);
	ma[p]=max(ma[p*2],ma[p*2|1]);
}
void update(int p,int pl,int pr,int x)
{
	if(pl==pr)
	{
		mi[p]=lt[pl],ma[p]=nx[pl];
		return ;
	}
	int mid=(pl+pr)>>1;
	if(x<=mid) update(p*2,pl,mid,x);
	else update(p*2|1,mid+1,pr,x);
	push_up(p);
}
void find(int p,int pl,int pr,int l,int r,vc<pi>&v)
{
	if(mi[p]>l&&ma[p]<r) return ;
	if(pl==pr)
	{
		if(mi[p]<l) v.push_back(pi(bel[pl],pl));
		if(ma[p]>r) v.push_back(pi(bel[pl],nx[pl]));
		return ;
	}
	int mid=(pl+pr)>>1;
	if(l<=mid) find(p*2,pl,mid,l,r,v);
	if(mid<r) find(p*2|1,mid+1,pr,l,r,v);
}
inline void cover(int l,int r)
{
	auto it=S1.lower_bound(l);
	while(it!=S1.end()&&*it<r) S1.erase(it),it=S1.lower_bound(l);
	it=S0.lower_bound(l);
	while(it!=S0.end()&&*it<r) S1.insert(*it),S0.erase(it),it=S0.lower_bound(l);
}
inline ll C(int c){ return (ll)c*(c-1)/2;}
inline void run(int L,int P1,int P2)
{
	ans-=C(cnt[L]);
	vc<int>v[2];int i=root[L],j=P1,f=-1;//哪个小
	while(true)
	{
		v[0].push_back(i),v[1].push_back(j);
		if(nx[i]==i){ f=0;break;}
		else if(nx[j]==P2){ f=1;break;}
		i=nx[i]==P1?P2:nx[i],j=nx[j];
	}
	int N1=lt[P1],N2=lt[P2];
	lt[P1]=P1,nx[N2]=N2;nx[N1]=P2,lt[P2]=N1;
	update(1,1,n,P1),update(1,1,n,P2);
	update(1,1,n,N1),update(1,1,n,N2);

	c++;cnt[c]=0;
	root[c]=v[f].front();
	for(int i:v[f]) bel[i]=c,cnt[L]--,cnt[c]++;
	ans+=C(cnt[L])+C(cnt[c]);
	root[L]=v[1-f].front();
}
inline void run(int L,int P)
{
	ans-=C(cnt[L]);
	vc<int>v[2];int i=root[L],j=P,f=-1;
	while(true)
	{
		v[0].push_back(i),v[1].push_back(j);
		if(nx[i]==P){ f=0;break;}
		else if(nx[j]==j){ f=1;break;}
		i=nx[i],j=nx[j];
	}
	int N=lt[P];
	nx[N]=N,lt[P]=P;
	update(1,1,n,N),update(1,1,n,P);

	c++;cnt[c]=0;
	root[c]=v[f].front();
	for(int i:v[f]) bel[i]=c,cnt[L]--,cnt[c]++;
	ans+=C(cnt[L])+C(cnt[c]);
	root[L]=v[1-f].front();
}
inline void run()
{
	int l=read(),r=read();
	if(l>r) swap(l,r);
	if(l==r) return ;

	vc<pi>v;find(1,1,n,l,r-1,v);cover(l,r);
	sort(v.begin(),v.end());

	// for(auto i:v) printf("(%d,%d)\n",i.first,i.second);
	for(unsigned i=0;i<v.size();i++)
	{
		if(i+1<v.size()&&v[i].first==v[i+1].first)
		{
			run(v[i].first,v[i].second,v[i+1].second);
			i++;
		}
		else run(v[i].first,v[i].second);
	}
}
inline void output()
{
	return ;
	printf("output ans=%lld %d %d\n",ans,(int)S0.size(),(int)S1.size());
	printf("S0 : ");for(int i:S0) printf("%d ",i);;putchar('\n');
	printf("S1 : ");for(int i:S1) printf("%d ",i);;putchar('\n');
	for(int i=1;i<n;i++) printf("i=%d : bel=%d lt=%d nx=%d\n",i,bel[i],lt[i],nx[i]);
	for(int i=1;i<=c;i++) printf("%d : cnt=%d root=%d\n",i,cnt[i],root[i]);
}
inline void solve()
{
	S0.clear(),S1.clear();
	n=read(),m=read(),c=0;
	if(n==1)
	{
		for(int i=1;i<=m;i++)
		{
			assert(read()==1&&read()==1);
			printf("0\n");
		}
		return ;
	}

	c=1;cnt[1]=n-1,root[1]=1,ans=C(n-1);
	for(int i=1;i<n;i++)
	{
		nx[i]=min(n-1,i+1);
		lt[i]=max(1,i-1);
		bel[i]=1;
		update(1,1,n,i);
		S0.insert(i);
	}
	output();

	for(int i=1;i<=m;i++)
	{
		run();
		ll o=ans+(ll)S0.size()*(n-1-S0.size()+i)+S1.size();
		printf("%lld\n",o);output();
	}
}
int main()
{
	int T=read();
	while(T--) solve();
	return 0;
}
/*
1
7 4
2 6
3 5
1 6
4 7
*/