const   cif:array['0'..'9'] of byte=(0,1,2,3,4,5,6,7,8,9);
type    adr=^noduri;
        noduri=record val:longint; urm:adr; end;
        vector=array[1..100010] of longint;
var     {
         S - valorile sortate
         T - timpi
         L - liste
         E - existenta (pentru dfs)
         V - valori (cati "subordonati" are fiecare nod)
        }
        L:array[1..100010] of adr;
        V,T,S,C:vector;
        E:array[1..100010] of boolean;
        n,i,j,k2,max:longint;
        ss:string[15];
        x,k1,ks:byte;
        q:adr;
        f,g:text;

function poz(a,b:longint):longint;
var i,j:shortint;
    t:longint;
begin
  i:=0; j:=-1;
  while a<b do
    begin
      if v[S[a]]<v[S[b]] then
        begin
          t:=S[a]; S[a]:=S[b]; S[b]:=t;
          t:=i; i:=-j; j:=-t;
        end;
      inc(a,i); inc(b,j);
    end;
  poz:=a;
end;

procedure sort(a,b:longint);
var m:longint;
begin
  if a<b then
    begin
      m:=poz(a,b);
      sort(a,m-1);
      sort(m+1,b);
    end;
end;

procedure df(nod:longint);
var p:adr;
begin
  E[nod]:=true;
  p:=L[nod];
  while p<>nil do
    begin
      if not E[p^.val] then df(p^.val);
      inc(v[nod],v[p^.val]);
      p:=p^.urm;
    end;
end;

procedure zvon;
var q:adr; k,i,p,u:longint;
begin
  p:=1; u:=1; C[1]:=1;
  while p<=u do
    begin
      q:=L[C[p]];
      k:=0;
      while q<>nil do
        begin
          inc(k);
          S[k]:=q^.val;
          q:=q^.urm;
        end;
      sort(1,k);
      for i:=1 to k do
        begin
          T[S[i]]:=T[C[p]]+i;
          if T[S[i]]>max then max:=T[S[i]];
          inc(u);
          C[u]:=S[i];
        end;
      inc(p);
    end;
end;

begin
  assign(f,'zvon.in');
  reset(f);
  assign(g,'zvon.out');
  rewrite(g);
  readln(f,x);
  for k1:=1 to x do
    begin
      readln(f,n);
      for i:=1 to n do L[i]:=nil;
      for i:=1 to n do V[i]:=0;
      for i:=1 to n do E[i]:=false;
      for k2:=1 to n-1 do
        begin
          readln(f,ss);
          ks:=1;
          i:=0; j:=0;
          while ss[ks]<>' ' do
            begin
              i:=i*10+cif[ss[ks]];
              inc(ks);
            end;
          inc(ks);
          while ks<=length(ss) do
            begin
              j:=j*10+cif[ss[ks]];
              inc(ks);
            end;
          inc(v[i]);
          new(q);
          q^.val:=j; q^.urm:=L[i];
          L[i]:=q;
        end;
      df(1);
      T[1]:=0;
      max:=0;
      zvon;
      writeln(g,max);
    end;
  close(f);
  close(g);
end.