#include<bits/stdc++.h>
#define fi first
#define se second
#define pub emplace_back
#define mk make_pair
using namespace std;
typedef long long ll;
int read(){
	char c=getchar();int x=0;
	while(!isdigit(c)) c=getchar();
	while(isdigit(c)) x=x*10+(c^48),c=getchar();
	return x;
}
const int N=2.5e5+10;
mt19937 rd(84320);
int n;
vector<int> v1,v2;
unordered_set<int> s;
ll res2;
struct CT{
	set<int> s;
	vector<int> v;
	int res;
	void clean(){
		res=0;
		s.clear();
	}
	void del(int l,int r){
		auto it=s.lower_bound(l);
		v.clear();
		while(it!=s.end()&&*it<=r){
			res--;
			auto itt=it;it++;
			v.pub(*itt);
			s.erase(itt);
		}
	}
	void add(const vector<int> &dt){
		for(const int &x:dt) s.insert(x),res++;
	}
}s0,s1;
struct FHQ{
	struct T{
		int ls,rs;
		int rnd,sz,fa;
	}t[N];int ts;//t[0].sz must be 0
	inline void psu(int p){
		if(!p) return;
		t[p].fa=0;
		t[p].sz=t[t[p].ls].sz+t[t[p].rs].sz+1;
		t[t[p].ls].fa=t[t[p].rs].fa=p;
	}
	void split(int p,int key,int &x,int &y){
		if(!p) return x=y=0,void();
		if(p<=key){
			x=p;
			split(t[p].rs,key,t[x].rs,y);
			psu(x);
		}else{
			y=p;
			split(t[p].ls,key,x,t[y].ls);
			psu(y);
		}
	}
	int merge(int x,int y){
		if(!x||!y) return psu(x+y),x+y;
		if(t[x].rnd>t[y].rnd){
			t[x].rs=merge(t[x].rs,y);
			return psu(x),x;
		}else{
			t[y].ls=merge(x,t[y].ls);
			return psu(y),y;
		}
	}
	int New(){
		t[++ts]={0,0,(int)rd(),1,0};
		return ts;
	}
	int getfa(int x){
		while(t[x].fa) x=t[x].fa;
		return x;
	}
	void dt(int rt,int op){//rt must be [1,n]
		res2+=op*(ll)t[rt].sz*(t[rt].sz-1)/2;
	}
	void ch(int rt,int l,int r){
		dt(rt,-1);
		int x,y,z;
		split(rt,l-1,x,y);
		split(y,r,y,z);
		x=merge(x,z);
		dt(x,1);dt(y,1);
	}
	int getsz(int p){
		int res=t[t[p].ls].sz+1;
		while(t[p].fa){
			int to=t[p].fa;
			if(t[to].rs==p) res+=t[t[to].ls].sz+1;
			p=to;
		}
		return res;
	}
	int get(int rt,int lim){
		if(t[rt].sz<lim) return -1;
		if(lim==0) return -1;
		int p=rt;
		while(t[p].ls||t[p].rs){
			int ck=t[t[p].ls].sz+1;
			if(lim>ck) lim-=ck,p=t[p].rs;
			else if(lim==ck) return p;
			else p=t[p].ls;
		}
		return p;
	}
}t2;
struct SGT{
	struct T{
		int l,r;
		int mi,mx;
	}t[N*4];
	void psu(int p){
		t[p].mi=min(t[p*2].mi,t[p*2+1].mi);
		t[p].mx=max(t[p*2].mx,t[p*2+1].mx);
	}
	void build(int p,int l,int r){
		t[p].l=l,t[p].r=r;
		if(l==r){
			t[p].mi=l==1?1:l-1;
			t[p].mx=l==n?n:l+1;
			return;
		}
		int mid=l+r>>1;
		build(p*2,l,mid);
		build(p*2+1,mid+1,r);
		psu(p);
	}
	void solve(int p,int x,int y){
		if(x<=t[p].mi&&t[p].mx<=y) return;
		if(t[p].l==t[p].r){
			int id=t[p].l;
			s.insert(t2.getfa(id));
			if(t[p].mi<x) v2.pub(t[p].mi),t[p].mi=id;
			if(t[p].mx>y) v1.pub(t[p].mx),t[p].mx=id;
			return;
		}
		int mid=t[p].l+t[p].r>>1;
		if(x<=mid) solve(p*2,x,y);
		if(y>mid) solve(p*2+1,x,y);
		psu(p);
	}
	void ch1(int p,int x,int dt){
		if(t[p].l==t[p].r) return t[p].mi=dt,void();
		int mid=t[p].l+t[p].r>>1;
		if(x<=mid) ch1(p*2,x,dt); else ch1(p*2+1,x,dt);
		psu(p);
	}
	void ch2(int p,int x,int dt){
		if(t[p].l==t[p].r) return t[p].mx=dt,void();
		int mid=t[p].l+t[p].r>>1;
		if(x<=mid) ch2(p*2,x,dt); else ch2(p*2+1,x,dt);
		psu(p);
	}
}t1;
void work(){
	s0.clean(),s1.clean();
	t2.ts=0;
	n=read();
	int qs=read();
	n--;
	t1.build(1,1,n);
	for(int i=1,lst=0;i<=n;i++) lst=t2.merge(lst,t2.New());
	vector<int> v;
	for(int i=1;i<=n;i++) v.pub(i);
	s0.add(v);
	res2=(ll)n*(n-1)/2;
	for(int i=1;i<=qs;i++){
		int l=read(),r=read();
		if(l>r) swap(l,r);
		r--;
		if(l>r){
			printf("%lld\n",s1.res+res2+(ll)s0.res*(n+i-s0.res));
			continue;
		}
		v1.clear(),v2.clear(),s.clear();
		t1.solve(1,l,r);
		for(int rt:s) t2.ch(rt,l,r);
		for(int x:v1){
			int rk=t2.getsz(x);
			int res=t2.get(t2.getfa(x),rk-1);
			if(res==-1) res=x;
			t1.ch1(1,x,res);
		}
		for(int x:v2){
			int rk=t2.getsz(x);
			int res=t2.get(t2.getfa(x),rk+1);
			if(res==-1) res=x;
			t1.ch2(1,x,res);
		}
		s0.del(l,r);
		s1.del(l,r);
		s1.add(s0.v);
		//cerr<<i<<":"<<s0.res<<' '<<s1.res<<' '<<res2<<endl;
		printf("%lld\n",s1.res+res2+(ll)s0.res*(n+i-s0.res));
	}
}

int main(){
//	auto file1=freopen("dd.in","r",stdin);
//	auto file2=freopen("dd.out","w",stdout);
	int tt=read();while(tt--) work();
	return 0;
}