/*
  [BAPC'06] MAKE IT MANHATTAN (slow solution)
  by: Jan Kuipers
*/

using namespace std;

#include <iostream>
#include <vector>

int main () {

  int runs;
  cin>>runs;
  while (runs--) {

    int S,B;
    cin>>S>>B;
    
    vector<int> x(B), y(B);
    for (int i=0; i<B; i++) cin>>x[i]>>y[i];

    int res=INT_MAX;    
    for (int thex=0; thex<S; thex++)
      for (int they=0; they<S; they++) {
	int tmp=0;
	for (int i=0; i<B && tmp<res; i++) 
	  if ((x[i]%S+S)%S==thex || (y[i]%S+S)%S==they) tmp++;
	res <?= tmp;
      }
    
    cout<<res<<endl;
  }
  
  return 0;
}
