#include<bits/stdc++.h>
using namespace std;
#define L (k<<1)
#define R (L|1)
#define mid (l+r>>1)
typedef long long ll;
typedef pair<int,int> pii;
const int N=250005;
int t,n,m,s,x,y,id[N],pre[N],nex[N],sz[N],fl[N<<2],fr[N<<2];
ll ans;
vector<int>vl,vr;
set<int>S0,S1;
set<int>::iterator it;
bool cmp(int x,int y){
    return id[x]<id[y];
}
ll C(int n){
    return (ll)n*(n-1)/2;
}
void update(int k,int l,int r,int x){
    if (l==r){
        fl[k]=pre[x],fr[k]=nex[x];
        return;
    }
    if (x<=mid)update(L,l,mid,x);
    else update(R,mid+1,r,x);
    fl[k]=min(fl[L],fl[R]),fr[k]=max(fr[L],fr[R]);
}
void query(int k,int l,int r,int x,int y){
    if ((l>y)||(x>r)||(fl[k]>=x)&&(fr[k]<=y))return;
    if (l==r){
        if (fl[k]<x)vl.push_back(l),fl[k]=n;
        if (fr[k]>y)vr.push_back(l),fr[k]=0;
        return;
    }
    query(L,l,mid,x,y),query(R,mid+1,r,x,y);
    fl[k]=min(fl[L],fl[R]),fr[k]=max(fr[L],fr[R]);
}
void split(int x){
    int k=id[x],y=nex[x];
    nex[x]=0,pre[y]=n;
    update(1,1,n-1,x),update(1,1,n-1,y);
    int a=x,b=y;
    while ((a<n)&&(b))a=pre[a],b=nex[b];
    sz[++s]=0;
    if (a==n){
        for(int i=x;i<n;i=pre[i])id[i]=s,sz[s]++;
    }
    else{
        for(int i=y;i;i=nex[i])id[i]=s,sz[s]++;
    }
    ans-=C(sz[k]),sz[k]-=sz[s],ans+=C(sz[k])+C(sz[s]);
}
void split(int x,int y){
    int k=id[x],l=pre[x],r=nex[y];
    nex[l]=r,pre[r]=l,pre[x]=n,nex[y]=0;
    update(1,1,n-1,l),update(1,1,n-1,r);
    int a=l,b=x,c=r;
    while ((a<n)&&(b))a=pre[a],b=nex[b];
    while ((b)&&(c))b=nex[b],c=nex[c];
    sz[++s]=0;
    if (!b){
        for(int i=x;i;i=nex[i])id[i]=s,sz[s]++;
    }
    else{
        for(int i=l;i<n;i=pre[i])id[i]=s,sz[s]++;
        for(int i=r;i;i=nex[i])id[i]=s,sz[s]++;
    }
    ans-=C(sz[k]),sz[k]-=sz[s],ans+=C(sz[k])+C(sz[s]);
}
int main(){
    scanf("%d",&t);
    while (t--){
        scanf("%d%d",&n,&m);
        s=0,S0.clear(),S1.clear();
        for(int i=1;i<n;i++)S0.insert(i);
        for(int i=1;i<n;i++){
            id[i]=0;
            pre[i]=(i==1 ? n : i-1);
            nex[i]=(i==n-1 ? 0 : i+1);
        }
        sz[0]=n-1,ans=C(n-1);
        for(int i=1;i<n;i++)update(1,1,n-1,i);
        for(int i=1;i<=m;i++){
            scanf("%d%d",&x,&y);
            if (x>y)swap(x,y);
            for(it=S1.lower_bound(x);(it!=S1.end())&&((*it)<y);)it=S1.erase(it);
            for(it=S0.lower_bound(x);(it!=S0.end())&&((*it)<y);){
                S1.insert(*it);
                it=S0.erase(it);
            }
            vl.clear(),vr.clear();
            query(1,1,n-1,x,y-1);
            sort(vl.begin(),vl.end(),cmp);
            sort(vr.begin(),vr.end(),cmp);
            for(int x=0,y=0;(x<vl.size())||(y<vr.size());){
                if ((x<vl.size())&&(y<vr.size())&&(id[vl[x]]==id[vr[y]]))split(vl[x++],vr[y++]);
                else{
                    if ((x<vl.size())&&((y==vr.size())||(id[vl[x]]<id[vr[y]])))split(pre[vl[x++]]);
                    else split(vr[y++]);
                }
            }
            printf("%lld\n",(ll)S0.size()*(n+i-S0.size()-1)+S1.size()+ans);
        }
    }
    return 0;
}