#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=6e5+50,inf=1e9;

vector<int>p;

struct tree
{
    int ty,w[N],a[N];

    #define ls (x<<1)
    #define rs (x<<1|1)
    #define mid ((l+r)>>1)

    int chk(int a,int b)
    {
        return ty?min(a,b):max(a,b);
    }

    void build(int x,int l,int r)
    {
        if(l==r)
        {
            if(a[l])w[x]=a[l];
            else w[x]=ty?inf:0;
            return;
        }
        build(ls,l,mid);build(rs,mid+1,r);
        w[x]=chk(w[ls],w[rs]);
    }

    void find(int x,int l,int r,int L,int R,int l2,int r2)
    {
        if(L<=l&&R>=r)
        {
            if(w[x]<l2||w[x]>r2)return;
            if(l==r)p.push_back(w[x]);
            else find(ls,l,mid,L,R,l2,r2),find(rs,mid+1,r,L,R,l2,r2);
            return;
        }
        if(L<=mid)find(ls,l,mid,L,R,l2,r2);
        if(R>mid)find(rs,mid+1,r,L,R,l2,r2);
    }
    
    void insert(int x,int l,int r,int d,int rw)
    {
        if(l==r)return w[x]=(rw?rw:ty?inf:0),void();
        if(d<=mid)insert(ls,l,mid,d,rw);
        else insert(rs,mid+1,r,d,rw);
        w[x]=chk(w[ls],w[rs]);
    }
}pre,las;

int n,m,mi[N],la[N],tot,val[N],ch[N][2],fa[N],rd[N],T,sum[N],v[N],c0,c1;ll ans;

ll C(int n)
{
    return 1ll*n*(n-1)/2;
}

void clear()
{
    tot=ans=c0=c1=0;
    for(int i=1;i<=n;i++)pre.a[i]=las.a[i]=0;
}

int mkn(int w)
{
    val[++tot]=w;rd[tot]=rand();ch[tot][0]=ch[tot][1]=fa[tot]=sum[tot]=v[tot]=0;
    return tot;
}

int findroot(int x)
{
    return fa[x]?findroot(fa[x]):x;
}

void build(int x,int l,int r)
{
    mi[x]=la[x]=0;
    if(l==r)return;
    build(ls,l,mid);build(rs,mid+1,r);
}

void down(int x)
{
    int&w=la[x];
    la[ls]+=w;mi[ls]+=w;
    la[rs]+=w;mi[rs]+=w;
    w=0;
}

void dfs(int x,int l,int r)
{
    if(mi[x]>2)return;
    if(l==r)
    {
        if(mi[x]==1)
        {
            c0--,c1++;
            v[l]=1;int ro=l;
            while(l)++sum[l],ro=l,l=fa[l];
            ans-=C(sum[ro]-1)-C(sum[ro]);
        }
        if(mi[x]==2)c1--;
        return;
    }
    down(x);dfs(ls,l,mid);dfs(rs,mid+1,r);
}

void insert(int x,int l,int r,int L,int R)
{
    if(L<=l&&R>=r)
    {
        mi[x]++;la[x]++;
        return dfs(x,l,r);
    }
    down(x);
    if(L<=mid)insert(ls,l,mid,L,R);
    if(R>mid)insert(rs,mid+1,r,L,R);
    mi[x]=min(mi[ls],mi[rs]);
}

void solve(ll tot)
{
    cout<<c0*(tot-1)-C(c0)+c1+ans<<'\n';
}

void up(int x)
{
    sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+v[x];
}

int merge(int a,int b,int f)
{
    if(a+b==0)return 0;
    if(!a||!b){fa[a+b]=f;return a+b;}
    if(rd[a]<rd[b])
    {
        ch[a][1]=merge(ch[a][1],b,a);
        fa[a]=f;up(a);return a;
    }
    ch[b][0]=merge(a,ch[b][0],b);
    fa[b]=f;up(b);return b;
}

void split(int x,int k,int&a,int&b,int Fa,int Fb)
{
    if(!x)return a=b=0,void();
    if(x<=k)a=x,fa[x]=Fa,split(ch[x][1],k,ch[x][1],b,x,Fb);
    else b=x,fa[x]=Fb,split(ch[x][0],k,a,ch[x][0],Fa,x);
    up(x);
}

int findl(int x)
{
    return ch[x][0]?findl(ch[x][0]):x;
}

int findr(int x)
{
    return ch[x][1]?findr(ch[x][1]):x;
}

void solve(int x,int l,int r)
{
    int ro=findroot(x);
    ans-=C(sum[ro]);
    int a=0,b=0,c=0;
    split(ro,l-1,a,b,0,0);split(b,r,b,c,0,0);
    int ra=findr(a),lb=findl(b),rb=findr(b),lc=findl(c);
    if(ra)pre.insert(1,1,n,ra,lc),las.insert(1,1,n,lb,0);
    if(lc)las.insert(1,1,n,lc,ra),pre.insert(1,1,n,rb,0);
    a=merge(a,c,0);
    ans+=C(sum[a])+C(sum[b]);
}

void sol()
{
    cin>>n>>m;n--;
    c0=n,c1=0;pre.ty=0,las.ty=1;
    for(int i=1;i<n;i++)las.a[i+1]=i,pre.a[i]=i+1;
    int ro=mkn(1);
    for(int i=2;i<=n;i++)ro=merge(ro,mkn(i),0);
    build(1,1,n);las.build(1,1,n);pre.build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        int l,r;cin>>l>>r;
        if(l==r){solve(n+i);continue;}
        if(l>r)swap(l,r);r--;
        insert(1,1,n,l,r);
        vector<int>().swap(p);
        las.find(1,1,n,l,r,1,l-1);
        for(auto x:p)solve(x,l,r);
        vector<int>().swap(p);
        pre.find(1,1,n,l,r,r+1,n);
        for(auto x:p)solve(x,l,r);
        solve(n+i);
    }
}

main()
{
    cin>>T;T=min(T,17);
    while(T--)sol(),clear();
}