#include<bits/stdc++.h>
#define For(i,j,k) for(int i=(j);i<=(k);++i)
#define ForDown(i,j,k) for(int i=(j);i>=(k);--i)
#define Debug(fmt, args...) fprintf(stderr,"In function %s on line #%d: " fmt, __func__, __LINE__, ##args),fflush(stderr)
#define debug(fmt, args...) fprintf(stderr,fmt,##args),fflush(stderr)
#define within :
#define LJY main
using namespace std;
typedef long long ll;
const int N=2.5e5+5;
mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
inline int read(){
  char ch=getchar();int x=0,f=1;
  while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
  while(ch>='0'&&ch<='9')
    x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
  return x*f;
}
int n,m;
int pre[N],suf[N],bel[N],siz[N],cnt;ll ans;
int fa[N],S;set<int>st;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline ll C(ll x){return x*(x-1)/2;}
vector<int>v1,v2;
int Tl[N<<2],Tr[N<<2];
void build(int l=1,int r=n-1,int rt=1){
  if(l==r){Tl[rt]=pre[l];Tr[rt]=suf[l];return;}
  int mid=(l+r)>>1;
  build(l,mid,rt<<1);build(mid+1,r,rt<<1|1);
  Tl[rt]=min(Tl[rt<<1],Tl[rt<<1|1]);
  Tr[rt]=max(Tr[rt<<1],Tr[rt<<1|1]);
}
int debug_cnt;
void query(int L,int R,int l=1,int r=n-1,int rt=1){
  if((Tl[rt]>=L&&Tr[rt]<=R)||l>R||r<L) return;
  assert((++debug_cnt)<=1e8);
  if(l==r){
    if(Tl[rt]<L) v1.emplace_back(l),Tl[rt]=n;
    if(Tr[rt]>R) v2.emplace_back(r),Tr[rt]=0;
    return;
  }int mid=(l+r)>>1;
  query(L,R,l,mid,rt<<1);query(L,R,mid+1,r,rt<<1|1);
  Tl[rt]=min(Tl[rt<<1],Tl[rt<<1|1]);
  Tr[rt]=max(Tr[rt<<1],Tr[rt<<1|1]);
}
void update(int L,int l=1,int r=n-1,int rt=1){
  assert((++debug_cnt)<=1e8);
  if(l==r){Tl[rt]=pre[l];Tr[rt]=suf[l];return;}
  int mid=(l+r)>>1;
  if(L<=mid) update(L,l,mid,rt<<1);
  else update(L,mid+1,r,rt<<1|1);
  Tl[rt]=min(Tl[rt<<1],Tl[rt<<1|1]);
  Tr[rt]=max(Tr[rt<<1],Tr[rt<<1|1]);
}
void split(int x){
  int id=bel[x],y=suf[x];
  suf[x]=0;pre[y]=n;update(x);update(y);
  int p1=x,p2=y;while(p1<n&&p2) p1=pre[p1],p2=suf[p2];siz[++cnt]=0;
  if(p1==n) for(int i=x;i<n;i=pre[i]) siz[cnt]++,bel[i]=cnt;
  else for(int i=y;i;i=suf[i]) siz[cnt]++,bel[i]=cnt;
  ans-=C(siz[id]);siz[id]-=siz[cnt];ans+=C(siz[id])+C(siz[cnt]);
}
void split(int x,int y){
  int id=bel[x],a=pre[x],b=suf[y];
  suf[a]=b;pre[b]=a;pre[x]=n;suf[y]=0;
  update(a);update(b);
  int p1=a,p2=x,p3=b;
  while(p1<n&&p2) p1=pre[p1],p2=suf[p2];
  while(p3&&p2) p3=suf[p3],p2=suf[p2];
  siz[++cnt]=0;
  if(p2) for(int i=x;i;i=suf[i]) siz[cnt]++,bel[i]=cnt;
  else{
    for(int i=a;i<n;i=pre[i]) siz[cnt]++,bel[i]=cnt;
    for(int i=b;i;i=suf[i]) siz[cnt]++,bel[i]=cnt;
  }ans-=C(siz[id]);siz[id]-=siz[cnt];ans+=C(siz[id])+C(siz[cnt]);
}
void ljy(){
  n=read();m=read();
  if(n==1){For(i,1,m) read(),read(),puts("0");return;}
  S=n-1;siz[1]=n-1;ans=C(siz[1]);
  For(i,1,n-1) pre[i]=i-1,suf[i]=i+1,fa[i]=i,bel[i]=1;fa[n]=n;
  st.clear();cnt=1;pre[1]=n;suf[n-1]=0;build();
  For(_,1,m){
    int x=read(),y=read();if(x>y) swap(x,y);
    for(auto it=st.lower_bound(x);it!=st.end()&&*it<y;) it=st.erase(it);
    int now=find(x);while(now<y) st.insert(now),S--,fa[now]=now+1,now=find(now);
    v1.clear();v2.clear();query(x,y-1);int s1=v1.size(),s2=v2.size();
    sort(v1.begin(),v1.end(),[&](int x,int y){return bel[x]<bel[y];});
    sort(v2.begin(),v2.end(),[&](int x,int y){return bel[x]<bel[y];});
    for(int i=0,j=0;i<s1||j<s2;){
      if(i<s1&&j<s2&&bel[v1[i]]==bel[v2[j]]) split(v1[i++],v2[j++]);
      else if(i<s1&&(j==s2||bel[v1[i]]<bel[v2[j]])) split(pre[v1[i++]]);
      else split(v2[j++]);
    }printf("%lld\n",ans+(ll)S*(n+_-1-S)+st.size());
  }
}
signed LJY(){int T=read();while(T--) ljy();}