// BAPC06 Make it Manhattan, Marijn Kruisselbrink
import java.io.*;
import java.util.*;
       class Main {
	static MyScanner sc = new MyScanner();
	static class MyScanner {
		BufferedReader br;
		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		public int nextInt() {
			int n = 0;
			boolean neg = false;
			while (true) {
				int c = 0; try { c = br.read(); } catch (IOException e) {}
				if (c == '-') neg = true;
				else if (c >= '0' && c <= '9') {
					n *= 10;
					n += c - '0';
				} else return neg ? -n : n;
			}
		}
	}
//	static Scanner sc = new Scanner(System.in);
	public static void main(String[] arg) {
		int n = sc.nextInt(); while (n-->0) new Main().solve();
	}
	void solve() {
		int d = sc.nextInt();
		int b = sc.nextInt();
		int[] n = new int[d*d];
		int[] r = new int[d];
		int[] c = new int[d];
		while (b-->0) {
			int x = sc.nextInt() % d; if (x < 0) x += d;
			int y = sc.nextInt() % d; if (y < 0) y += d;
			n[x*d + y]++;
			r[x]++; c[y]++;
		}
		int min = Integer.MAX_VALUE;
		for (int x = 0; x < d; x++) for (int y = 0; y < d; y++) {
			int f = r[x] + c[y] - n[x*d+y];
			if (f < min) {min = f; 
//				System.err.printf("-> %d %d\n", x, y);
			}
		}
		System.out.printf("%d\n", min);
	}
}
