#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
const int maxn=8e5+10;
struct SegT{
    int num0[maxn<<2],num1[maxn<<2],tag[maxn<<2];
    inline void pushtg(int i,int v)
    {
    	tag[i]+=v;
        if(v==0)return;
        if(v==1)num1[i]=num0[i],num0[i]=0;
        else num1[i]=num0[i]=0;
    }
    inline void pushdown(int i)
    {
        if(!tag[i])return;
        pushtg(i<<1,tag[i]);
        pushtg(i<<1|1,tag[i]);
        tag[i]=0;
    }
    inline void update(int i,int l,int r,int L,int R)
    {
    	if(L>R)return;
        if(L<=l&&r<=R)return pushtg(i,1),void();
        int mid=l+r>>1;pushdown(i);
        if(L<=mid)update(i<<1,l,mid,L,R);
        if(R>mid)update(i<<1|1,mid+1,r,L,R);
        num0[i]=num0[i<<1]+num0[i<<1|1];
        num1[i]=num1[i<<1]+num1[i<<1|1];
        //printf("%d %d %d %d\n",l,r,num0[i],num1[i]);
    }
    inline void build(int i,int l,int r)
    {
        tag[i]=0;
        if(l==r){num0[i]=1;num1[i]=0;return;}
        int mid=l+r>>1;
        build(i<<1,l,mid);
        build(i<<1|1,mid+1,r);
        num0[i]=num0[i<<1]+num0[i<<1|1];
        num1[i]=num1[i<<1]+num1[i<<1|1];
    }
}T1;
int id[maxn];
int pre[maxn],nxt[maxn],Lp[maxn],siz[maxn];
struct SegTV{
    int mn[maxn<<2],mx[maxn<<2];
    inline void modifypre(int i,int l,int r,int p,int v)
    {
        if(l==r){pre[l]=mn[i]=v;return;}
        int mid=l+r>>1;
        if(p<=mid)modifypre(i<<1,l,mid,p,v);
        else modifypre(i<<1|1,mid+1,r,p,v);
        mn[i]=min(mn[i<<1],mn[i<<1|1]);
    }
    inline void modifynxt(int i,int l,int r,int p,int v)
    {
        if(l==r){nxt[l]=mx[i]=v;return;}
        int mid=l+r>>1;
        if(p<=mid)modifynxt(i<<1,l,mid,p,v);
        else modifynxt(i<<1|1,mid+1,r,p,v);
        mx[i]=max(mx[i<<1],mx[i<<1|1]);
    }
    inline void findL(int i,int l,int r,int L,int R,int v,vector< pair<int,int> > &vec)
    {
    	if(L>R)return;
        if(mn[i]>=v)return;
        if(l==r){vec.push_back({id[l],l});return;}
        int mid=l+r>>1;
        if(L<=mid)findL(i<<1,l,mid,L,R,v,vec);
        if(R>mid)findL(i<<1|1,mid+1,r,L,R,v,vec);
    }
    inline void findR(int i,int l,int r,int L,int R,int v,vector< pair<int,int> > &vec)
    {
    	if(L>R)return;
        if(mx[i]<=v)return;
        if(l==r){vec.push_back({id[nxt[l]],nxt[l]});return;}
        int mid=l+r>>1;
        if(L<=mid)findR(i<<1,l,mid,L,R,v,vec);
        if(R>mid)findR(i<<1|1,mid+1,r,L,R,v,vec);
    }
    inline void build(int i,int l,int r,int *pre,int *nxt)
    {
        if(l==r){mn[i]=pre[l];mx[i]=nxt[l];return;}
        int mid=l+r>>1;
        build(i<<1,l,mid,pre,nxt);
        build(i<<1|1,mid+1,r,pre,nxt);
        mx[i]=max(mx[i<<1],mx[i<<1|1]);
        mn[i]=min(mn[i<<1],mn[i<<1|1]);
    }
}T2;
inline int calc(int x){return x*(x-1)/2;}
int ans;

int n,m,lid;
inline void getlist(vector<int> &A)
{
    ++lid;
    Lp[lid]=A[0];
    siz[lid]=A.size();
   // printf("newlist %d\n",lid);
    for(int v:A)id[v]=lid;
}
inline void cut(int i){int t=pre[i];T2.modifypre(1,1,n-1,i,i);T2.modifynxt(1,1,n-1,t,t);}
inline void link(int i,int j){T2.modifynxt(1,1,n-1,i,j);T2.modifypre(1,1,n-1,j,i);}
inline void cut(int lst,int L,int R)
{
    ans-=calc(siz[lst]);
    vector<int> l1,l2;
    int ptr1=Lp[lst],ptr2=L;
    while(1)
    {
        l1.push_back(ptr1),l2.push_back(ptr2);
        int n1=nxt[ptr1]==L?R:nxt[ptr1],n2=nxt[ptr2]==R?ptr2:nxt[ptr2];
        if(n1==ptr1)
        {
            getlist(l1);
            Lp[lst]=L;
            siz[lst]-=l1.size();
            ans+=calc(l1.size());
            ans+=calc(siz[lst]);
            break;
        }
        else if(n2==ptr2)
        {
            getlist(l2);
            siz[lst]-=l2.size();
            ans+=calc(l2.size());
            ans+=calc(siz[lst]);
            break;
        }
        ptr1=n1,ptr2=n2;
    }
    int t=pre[L];
    cut(L);cut(R);link(t,R);
}
inline int qry(int t)
{
    return ans+T1.num0[1]*(n-1+t-T1.num0[1])+T1.num1[1];
}
inline void cut2(int lst,int L)
{
    ans-=calc(siz[lst]);
    vector<int> l1,l2;
    int ptr1=Lp[lst],ptr2=L;
    //printf("?%d %d\n",lst,L);
    while(1)
    {
        l1.push_back(ptr1),l2.push_back(ptr2);
        int n1=nxt[ptr1]==L?ptr1:nxt[ptr1],n2=nxt[ptr2];
    //    printf("->%d %d\n",ptr1,ptr2);
        if(n1==ptr1)
        {
            getlist(l1);
            Lp[lst]=L;
            siz[lst]-=l1.size();
            ans+=calc(l1.size());
            ans+=calc(siz[lst]);
            break;
        }
        else if(n2==ptr2) 
        {
            getlist(l2);
            siz[lst]-=l2.size();
            ans+=calc(l2.size());
            ans+=calc(siz[lst]);
            break;
        }
        ptr1=n1,ptr2=n2;
    }
    cut(L);
}
void solve()
{
    cin>>n>>m;
    if(n==1)
    {
    	for(int i=1;i<=m;i++)
    	{
    		int l,r;cin>>l>>r;
    		puts("0");
		}
		return;
	}
    lid=1;
    ans=calc(n-1);
    Lp[1]=1;siz[1]=n-1;
    for(int i=1;i<=n-1;i++)pre[i]=i-1,nxt[i]=i+1;
    pre[1]=1;nxt[n-1]=n-1;
    for(int i=1;i<=n-1;i++)id[i]=1;
    T1.build(1,1,n-1);
    T2.build(1,1,n-1,pre,nxt);
    for(int i=1;i<=m;i++)
    {
        int l,r;
        cin>>l>>r;
        if(l!=r)
        {
	        if(l>r)swap(l,r);r--;
	        T1.update(1,1,n-1,l,r);
	        vector< pair<int,int> > vec;
	        T2.findL(1,1,n-1,l,r,l,vec);
	        T2.findR(1,1,n-1,l,r,r,vec);
	        sort(vec.begin(),vec.end());
	        vec.resize(unique(vec.begin(),vec.end())-vec.begin());
	        for(int i=0;i<vec.size();i++)
	        {
	            if(i<vec.size()-1&&vec[i].first==vec[i+1].first)
	                cut(vec[i].first,vec[i].second,vec[i+1].second),i++;
	            else 
	                cut2(vec[i].first,vec[i].second);
	        }
	    }
        cout<<qry(i)<<endl;
    }
    return;
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0);
    int T;cin>>T;
    while(T--)solve();
    return 0;
}