import java.io.*;
import java.util.*;

class Salesman {
public static void main(String args[]) throws Exception {

int[][] distance = new int[1010][1010];
int[] f0 = new int[2000];
int[] f1 = new int[2000];
int[] togo = new int[2000];
int[] tocome = new int[2000];

PrintWriter out = new PrintWriter(new BufferedWriter(
new OutputStreamWriter(System.out)), true);
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

st.nextToken();
int t = (int) st.nval;

while (t > 0) {
st.nextToken();
int n = (int) st.nval;
st.nextToken();
int k = (int) st.nval;

for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
distance[i][j] = 0;

for (int j = 0; j < k; j++) {
st.nextToken();
int x = (int) st.nval;
st.nextToken();
int y = (int) st.nval;
distance[x][y]++;
}

for (int j = 0; j < n; j++) {
int previous = 0;
for (int i = n - 1; i >= 0; i--) {
distance[i][j] += previous;
previous = distance[i][j];
}
}
for (int i = 0; i < n; i++) {
int previous = 0;
for (int j = 0; j < n; j++) {
distance[i][j] += previous;
previous = distance[i][j];
}
}

togo[0] = 0;

for (int i = 1; i < n; i++)
togo[i] = togo[i - 1] + distance[i - 1][i];

tocome[n - 1] = 0;

for (int i = n - 2; i >= 0; i--)
tocome[i] = tocome[i + 1] + distance[i + 1][i];

f0[1] = distance[1][0];
f1[1] = distance[0][1];

for (int i = 2; i < n; i++) {
int optval0 = 1000000000;
int optval1 = 1000000000;
for (int j = 1; j < i; j++) {
optval0 = Math.min(optval0, distance[i][j - 1] + togo[i - 1]
- togo[j] + f1[j]);
optval1 = Math.min(optval1, distance[j - 1][i] + tocome[j]
- tocome[i - 1] + f0[j]);
}
f1[i] = optval1;
f0[i] = optval0;
}

out.println(Math.min(f0[n - 1] + distance[n - 2][n - 1], f1[n - 1]
+ distance[n - 1][n - 2]));
t--;
}
}
}