program MoebiusDames (input, output);

{ (c) 25/08/'97 Meinte Boersma
  Pascal-uitwerking van de NKP'97-opgave
     "Schaken op een Moebiusband"
}

const
   maxgrootte = 10;
   keer2 = 20;   { = maxgrootte*2 }

type
   band = array[0..keer2, 0..maxgrootte] of boolean;
      { true <--> vrij ;; (0,0) is linksboven }

var    {globaal}
   bord : band;
   n, m, run, R : integer;


function vrij (var x, y : integer) : boolean;
{ zoekt eerste vrije plaats op bord vanaf positie (x, y) incl.
 naar rechtsonder en levert true <==> nog posities over en in
 (x, y) laatste vrije (of anders: geprobeerde (=(2n, m)) )
 plaats }

var
   hebbes : boolean;

begin
   hebbes := false;
   while not hebbes and (y<m) do begin
      while not hebbes and (x<2*n) do begin
	 hebbes := bord[x, y];
	 x := x+1;
      end;
      if not hebbes then begin
	 x := 0;
      end;
      y := y+1;
   end;
   if hebbes then begin
      vrij := true;
      x := x-1;
      y := y-1;
   end else begin
      vrij := false;
   end;
end; { vrij }


procedure plaatsdame (x, y : integer);

var
   i, j : integer;

begin
   { horizontaal }
   for j := 0 to m-1 do begin
      bord[x, j] := false;
   end;
   { verticaal }
   for i := 0 to (2*n -1) do begin
      bord[i, y] := false;
   end;
   { kruis }
   for j := 0 to m-1 do begin
      bord[(x+m-j) mod m, j] := false;
      bord[(x+m+j) mod m, j] := false;
   end;
end; { plaatsdame }


function maxdames (dames, x, y : integer) : integer;

var
   kopie : band;     { kopie voor de backtracking }
   max, terug : integer;

begin
   max := dames;
   kopie := bord;
   while vrij(x, y) do begin
      plaatsdame(x, y);
      terug := maxdames(dames+1, x, y);
      if terug > max then begin
	 max := terug;
      end;
      bord := kopie;
      x := x+1;
      if x = 2*n then begin
	 { over de rand }
	 x := 0;
	 y := y+1;
      end;
   end;
   maxdames := max;
end; { maxdames }


procedure instantie;

var
   i, j : integer;

begin
   for i := 0 to (2*n -1) do begin
      for j := 0 to m-1 do begin
	 bord[i, j] := true;
      end;
   end;
   writeln(maxdames(0, 0, 0):1);
end; { instantie }


begin
   readln(R);
   for run := 1 to R do begin
      readln(n, m);
      instantie;
   end;
end.