(*
 * Program:  cityplanner_bram
 * Author:   Bram Kuijvenhoven (bram at kuijvenhoven.net)
 * Language: Pascal (FreePascal 2.x or higher recommended)
 * Notes:    Example/test solution to 'Make it Manhattan' problem of BAPC 2006
 *)

program cityplanner_bram;

{$mode objfpc}{$H+}

uses
  Classes, SysUtils, Math;

const
  MAX_S = 1000;
  MAX_B = 1000000;
  MAX_COORD = 1000000000;

var
  numTestCases,testCase:integer;
  i,j:integer;
  S,B:integer;
  x,y:integer;
  xCount,yCount:array[0..MAX_S-1] of integer;
  count:array[0..MAX_S-1,0..MAX_S-1] of integer;
  M:integer;
  
function Wrap(a,b:integer):integer;
begin
  Result:=a mod b;
  if Result<0 then Result+=b;
end;

begin

  readln(numTestCases);
  for testCase:=1 to numTestCases do
  begin
    readln(S,B);
    if (S<1) or (S>MAX_S) then raise Exception.CreateFmt('S = %d is out of range 1..%d',[S,MAX_S]);
    if (B<0) or (B>MAX_B) then raise Exception.CreateFmt('B = %d is out of range 0..%d',[B,MAX_B]);
    for i:=0 to S-1 do
    begin
      xCount[i]:=0;
      yCount[i]:=0;
      for j:=0 to S-1 do
        count[i,j]:=0;
    end;
    for i:=1 to B do
    begin
      readln(x,y);
      if abs(x)>MAX_COORD then raise Exception.CreateFmt('x[%d] = %d is out of range -%d..%d',[i,x,MAX_COORD,MAX_COORD]);
      if abs(y)>MAX_COORD then raise Exception.CreateFmt('y[%d] = %d is out of range -%d..%d',[i,y,MAX_COORD,MAX_COORD]);
      Inc(xCount[Wrap(x,S)]);
      Inc(yCount[Wrap(y,S)]);
      Inc(count[Wrap(x,S),Wrap(y,S)]);
    end;
    M:=High(Integer);
    for i:=0 to S-1 do for j:=0 to S-1 do M:=Min(M,xCount[i]+yCount[j]-count[i,j]);
    writeln(M);
  end;
  
end.

