//* Problem  : 2519 - Make it Manhattan 
//* Contest  : acm.tju.edu.cn
//* Origin   : Benelux Algorithm Programming Contest 2006
//* Type     : Solution
//* Date     : 2008.04.28
//* Author   : alt
//* Language : C++
//* Compiler : Microsoft Visual C++ 6.0
//* Algoritm : 

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

#define int64 long long

struct point{
	int x, y;
}a[100000];

int n, res, d;

int cx[1024];
int cy[1024];
int xy[1024][1024];

inline int get_int()
{
	int res = 0; char ch = getchar();
	while (!(ch >= '0')) ch = getchar();
	while (ch >= '0') 
	{
		res = 10 * res + ch - '0';
		ch = getchar();
	}
	return res;
} 


void solve()
{
	memset(xy, 0, sizeof(xy));
	memset(cx, 0, sizeof(cx));
	memset(cy, 0, sizeof(cy));
	res = n;
	for (int i = 0; i < n; i++)
	{
		cx[a[i].x % d]++;
		cy[a[i].y % d]++;
		xy[a[i].x % d][a[i].y % d]++;
	}
	for (int rx = 0; rx < d; rx++)
		for (int ry = 0; ry < d; ry++)
			res = min(res, cx[rx] + cy[ry] - xy[rx][ry]);
}

int main()
{
#ifdef _DEBUG
	freopen("1366", "r", stdin);
#endif
	int nt; //scanf("%d", &nt);
	nt = get_int();
	while (nt--)
	{
		//scanf("%d%d", &d, &n);
		d = get_int();
		n = get_int();
		for (int i = 0; i < n; i++)
		{
			//scanf("%lld%lld", &a[i].x, &a[i].y);
			a[i].x = get_int();
			a[i].y = get_int();
			a[i].x += 1000000000;
			a[i].y += 1000000000;
		}
		solve();
		printf("%d\n", res);
	}
	return 0;
}