#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],pre[MAXN],suf[MAXN];ll siz[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):
minn[id<<1|1]<=x?askL(L,R,x,id<<1|1,mid+1,r):0);
}
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):
maxx[id<<1]>=x?skR(L,R,x,id<<1,l,mid):0);
}
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--;
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]);
ll 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);
unordered_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;
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;
}
}
}
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);
// freopen("l.in","r",stdin);
// freopen("l.out","w",stdout);
int _;cin>>_;
while(_--) solve();
}