JAG Strikes Back

JAG is the new revolutionary game from the company $BEST$. Each game has $T$ rounds. In every round, the players get a map of $N$ territories. Exactly $N-1$ pairs of territories share a border, and the map is connected: for any two territories $u$ and $v$, you can walk from $u$ to $v$, possibly crossing other territories.

The players take territories in turns until all territories are chosen. Two rules apply:

• Moves cannot be skipped.
• A player cannot choose a territory that is already chosen by either player.

The distance between territories $u$ and $v$ is the fewest borders you must cross on a path from $u$ to $v$. The first player wants to minimize the distance between the two furthest territories that the first player chose. The second player wants to maximize that distance. Print the distance between the two furthest territories chosen by the first player when both players play optimally.

The first line contains the number of rounds $T$. Each round starts with a line containing $N$ ($3 \leq N \leq 10^5$), the number of territories. The next $N-1$ lines each contain two numbers $u$ and $v$, meaning territories $u$ and $v$ share a border. The sum of $N$ over all rounds does not exceed 200000.

Print $T$ lines. The $i$-th line contains the answer for the $i$-th round.