tsp

#include <vector>
#include <cassert>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <climits>
#include <fstream>
#include <sstream>
#include<ctype.h>

#define PI 3.1415926535897932384626433832795028841971693993751058209749Lf
#define INF 2000000000
#define INFI 1e37
#define pb push_back
#define PRINT(x)           cout << #x << "  " << x << endl
#define BUF 4096
#define MAX 1010
char ibuf[BUF];
int ipt = BUF;

int readInt() {
	while (ipt < BUF && ibuf[ipt] < '0') ipt++;
	if (ipt == BUF) {
		fread(ibuf, 1, BUF, stdin);
		ipt = 0;
		while (ipt < BUF && ibuf[ipt] < '0') ipt++;
	}
	int n = 0;
	while (ipt < BUF && ibuf[ipt] >= '0') n = (n*10)+(ibuf[ipt++]-'0');
	if (ipt == BUF) {
		fread(ibuf, 1, BUF, stdin);
		ipt = 0;
		while (ipt < BUF && ibuf[ipt] >= '0') n = (n*10)+(ibuf[ipt++]-'0');
	}
	return n;
}

using namespace std;
int t,n,k;
int d[MAX][MAX];
int d1[MAX],d2[MAX];
int sum1[MAX],sum2[MAX];
int main()
{
	int x,y;
	int i,j,k;
	t=readInt();
	while(t--)
	{
		n=readInt();
		k=readInt();
		memset(d,0, sizeof d);
		while(k--)
		{
			x=readInt();
			y=readInt();
			d[x+1][y+1]++;
		}

		for(x=n,k=n,y=1;y<=n;--k>0?x--:y++)
		{
			for(i=x,j=y;i<=n&&j<=n;++i,++j)
				d[i][j]=d[i][j-1]+d[i+1][j]-d[i+1][j-1]+d[i][j];

		}
		for(i=1;i+1<=n;i++)
		{
			sum1[i]=sum1[i-1]+d[i][i+1];
			sum2[i]=sum2[i-1]+d[i+1][i];
		}

		d1[1]=d[1][2];d2[1]=d[2][1];
		for(j=2;j<n;j++)
		{
			x=INF;
			for(i=1;i<j;i++)
				x=min(x,d2[i]+d[i][j+1]+sum2[j-1]-sum2[i]);
			d1[j]=x;
			x=INF;
			for(i=1;i<j;i++)
				x=min(x,d1[i]+d[j+1][i]+sum1[j-1]-sum1[i]);
			d2[j]=x;

		}
		printf("%d\n",min(d1[n-1]+d[n][n-1],d2[n-1]+d[n-1][n]));
	}


	return 0;
}