Alicja i Bob grają w grę na drzewie $T$ o $n$ wierzchołkach. Alicja chce zidentyfikować ukryty wierzchołek $x$. Jednak Bob jest przeciwnikiem i nie musi wybierać $x$ z góry.

Początkowo każdy wierzchołek $T$ jest uznawany za „możliwy” kandydat na $x$. W każdej turze Alicja wybiera wierzchołek $v$ i pyta o odległość od $v$ do $x$. Bob odpowiada nieujemną liczbą całkowitą $d$. Alicja następnie usuwa wszystkich kandydatów $u$ takich, że $\operatorname{dist}(u, v) \neq d$.

Odpowiedź Boba musi być zgodna z co najmniej jednym pozostałym kandydatem. Innymi słowy, po usunięciu przez Alicję wszystkich wierzchołków $u$ z $\operatorname{dist}(u, v) \neq d$ zbiór kandydatów musi nadal być niepusty. Z zastrzeżeniem tej zasady Bob wybiera swoje odpowiedzi, aby zmusić Alicję do użycia jak największej liczby zapytań.

Alicja wygrywa, gdy pozostanie dokładnie jeden kandydat. Alicja wybiera swoje zapytania optymalnie, aby zminimalizować liczbę zapytań.

Biorąc pod uwagę strukturę drzewa, znajdź minimalną liczbę zapytań potrzebną Alicji, aby zagwarantować zwycięstwo, niezależnie od strategii Boba.

Na przykład, jeśli Alicja zapyta o wierzchołek $v$, a Bob odpowie $d=2$, to wszystkie wierzchołki w odległości dokładnie $2$ od $v$ pozostają możliwe, a wszystkie pozostałe są usuwane.

Zapytanie o $v$ i otrzymanie odpowiedzi 2: zakreskowany wierzchołek jest pytany, kropkowane wierzchołki pozostają możliwe, a zwykłe wierzchołki są usuwane.

Wejście

Pierwszy wiersz zawiera jedną liczbę całkowitą $t$ ($1 \le t \le 10^5$), liczbę przypadków testowych.

Każdy przypadek testowy zaczyna się od jednej liczby całkowitej $n$ ($2 \le n \le 2000$), liczby wierzchołków.

Każdy z kolejnych $n-1$ wierszy zawiera dwie liczby całkowite $a_i$ i $b_i$ ($1 \le a_i,b_i \le n$, $a_i \ne b_i$), oznaczające krawędź drzewa.

Gwarantuje się, że krawędzie każdego przypadku testowego tworzą drzewo oraz że $\sum n^2 \le 2000^2$ dla wszystkich przypadków testowych.

Wyjście

Dla każdego przypadku testowego wypisz jedną liczbę całkowitą: minimalną liczbę zapytań, jakich Alicja potrzebuje w najgorszym przypadku.

Przykład

Wejście 1

2
4
1 2
2 3
3 4
5
1 2
1 3
1 4
1 5

Wyjście 1

1
3

Uwagi 1

• W pierwszym przypadku testowym drzewo jest ścieżką o czterech wierzchołkach. Zapytanie o wierzchołek 1 daje możliwe odległości 0, 1, 2, 3, wszystkie różne, więc wystarczy jedno zapytanie.
• W drugim przypadku testowym drzewo jest gwiazdą z centrum w wierzchołku 1:
• Na poniższych rysunkach zakreskowany wierzchołek to pytany wierzchołek, kropkowane wierzchołki pozostają możliwe po odpowiedzi Boba, a zwykłe wierzchołki zostały usunięte.

Zapytanie 2, odpowiedź 2: wierzchołki 3, 4, 5 pozostają możliwe.

Zapytanie 3, odpowiedź 2: wierzchołki 4, 5 pozostają możliwe.

Zapytanie 4, odpowiedź 2: pozostaje tylko wierzchołek 5.

• To pokazuje, że trzy zapytania są wystarczające. Alicja najpierw pyta o liść 2. Jeśli Bob odpowie 0 lub 1, ukryty wierzchołek jest natychmiast określony; najgorsza odpowiedź to 2, pozostawiając liście 3, 4, 5. Następnie Alicja pyta o liść 3, a w najgorszym przypadku pozostają liście 4, 5. Jedno końcowe zapytanie je rozróżnia.
• Dwa zapytania nie wystarczą. Po pierwszym zapytaniu Bob może pozostawić co najmniej trzy możliwe liście. Wśród trzech liści gwiazdy jedno dodatkowe zapytanie o odległość nie może ich wszystkich rozróżnić, ponieważ co najmniej dwa liście mają tę samą odległość do pytanego wierzchołka.