Wszyscy wiedzą, że na Uniwersytecie Jagiellońskim bardzo kochamy rośliny. Stworzyliśmy setki zadań o drzewach, lasach, a nawet kaktusach! Niestety, zadania o zwierzętach nie są aż tak popularne. Dzisiaj chcemy udowodnić, że kochamy również zwierzęta.

Mówimy, że graf jest meduzą (jellyfish), jeśli jest to prosty, spójny graf nieskierowany o równej liczbie wierzchołków i krawędzi. Dana jest meduza $J$ o $n$ wierzchołkach. Dla dowolnego podzbioru wierzchołków $S \subseteq J$ mówimy, że $S$ jest niesamowitym podzbiorem, jeśli dla każdego $T \subseteq S$ istnieje spójny podgraf meduzy, który zawiera każdy wierzchołek z $T$ i nie zawiera żadnego innego wierzchołka z $S$.

Jaki jest maksymalny możliwy rozmiar niesamowitego podzbioru $J$?

Wejście

Pierwsza linia wejścia zawiera liczbę przypadków testowych $z$. Następnie następują opisy przypadków testowych.

Pierwsza linia każdego przypadku testowego zawiera jedną liczbę całkowitą $n$ ($3 \le n \le 100\,000$) – liczbę wierzchołków meduzy.

Kolejne $n$ linii zawiera po dwie liczby całkowite $u_i, v_i$ ($1 \le u_i \neq v_i \le n$), odpowiadające krawędziom meduzy. Gwarantuje się, że podany graf jest meduzą oraz że każde dwa wierzchołki są połączone co najwyżej jedną krawędzią.

Łączna liczba wierzchołków we wszystkich przypadkach testowych nie przekracza $10^6$.

Wyjście

Dla każdego przypadku testowego wypisz w pojedynczej linii jedną liczbę całkowitą – maksymalny możliwy rozmiar niesamowitego podzbioru meduzy.

Przykład

Wejście 1

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

Wyjście 1

4
3