program Cowboys;

{$APPTYPE CONSOLE}
{$R-}


uses
  SysUtils;

const
  top = 1000;

var
  tests, test, n, m, i, j, a, b, ii, jj: integer;
  links: array [1..top, 1..top] of boolean;
  complete: array [1..top] of boolean;
  busy: array [1..top] of boolean;
  k: array [1..top] of boolean;
  f1: text;
  eq: boolean;
  res: integer;

procedure find(where: integer; add_to: integer = -1);
var i: integer;
begin
  if not busy[where] then begin
  busy[where] := true;
  for i := 1 to n do begin
    if not (add_to = -1) and links[where, i] then
      links[add_to, i] := true;
    if links[where, i] and (not busy[i] or not complete[where]) then
      find(i, where);
  end;
  busy[where] := false;
  complete[where] := true;
  end;
end;

begin
Assign(f1, 'COWBOYS.IN');
reset(f1);
readln(f1, tests);
for test := 1 to tests do begin
  readln(f1, n, m);
  if m = 0 then
    writeln(0)
  else begin

  for i := 1 to m do begin
    readln(f1, a, b);
    links[a, b] := true;
    links[b, a] := true;
  end;

  for i := 1 to n do begin
    find(i);
    k[i] := true;
  end;

  for i := 1 to n do begin
    if k[i] then
      for j := i+1 to n do begin
        eq := true;
        for ii := 1 to n do
          if not (links[i, ii] = links[j, ii]) then begin
            eq := false;
            break;
          end;
        if eq then k[j] := false;
      end;
  end;

  res := 0;
  for i := 1 to n do begin
    if k[i] then inc(res);
  end;

  writeln(res);
  end;

end;




end.
