/*
  [BAPC'06] MAKE IT MANHATTAN
  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> cntx(S,0), cnty(S,0);
    vector<vector<int> > cntxy(S, vector<int>(S,0));

    for (int i=0; i<B; i++) {
      int x,y;
      cin>>x>>y;
      x=(x%S+S)%S;
      y=(y%S+S)%S;
      cntx[x]++;
      cnty[y]++;
      cntxy[x][y]++;
    }

    int res=INT_MAX;    
    for (int x=0; x<S; x++)
      for (int y=0; y<S; y++)
	res <?= cntx[x]+cnty[y]-cntxy[x][y];
    
    cout<<res<<endl;
  }
  
  return 0;
}
