h2. Date de intrare

Fişierul de intrare $revolta.in$ ...

Fişierul de intrare $revolta.in$ va conţine pe prima linie un singur număr, t, reprezentând numărul de teste. Fiecare test va începe cu numărul de sisteme din galaxie, n, urmat de n-1 linii de forma a b, reprezentând câte o gaura de vierme între sistemele a şi b.

h2. Date de ieşire

În fişierul de ieşire $revolta.out$ ...

În fişierul de ieşire $revolta.out$ se va afişa, fiecare test, o linie conţinând numărul minim de salturi care se poate obţine după înlocuire. Dacă numărul iniţial de salturi era deja optim, se va afişa acesta.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $2 ≤ n ≤ 1000000$

h2. Exemplu