#include<bits/stdc++.h>
#define F(i,a,b) for(i=(a);i<=(b);i++)
using namespace std;
const int _=5005;
inline void Max(int &x,int y){y>x?x=y:0;}
int N,n,q,x,y,s,a[_],d[_][_][2],i,j;
int P(){
	cin>>n>>q;
	F(i,0,n)a[i]=7,memset(d[i],0xc0,sizeof(d[i]));
	while(q--){cin>>x>>y;a[x]&=5;a[y]&=2;while(++x<y)a[x]&=3;}
	d[0][0][0]=0;
	F(i,0,n-1)F(j,0,i){
		x=a[i+1];
		if(x&1)Max(d[i+1][j][0],d[i][j][0]+i);
		if(x&2)Max(d[i+1][j+1][1],d[i][j][0]+j);
		if((x&5)==5)Max(d[i+1][j][0],d[i][j][1]+i);
		if(x&2)Max(d[i+1][j+1][1],d[i][j][1]+j);
	}
	s=-1;F(i,0,n)Max(s,d[n][i][0]),Max(s,d[n][i][1]);
	return s;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;while(N--)cout<<P()<<'\n';
}