Problem Statement

You are given a tree $T$ with $N$ vertices numbered $1$ to $N$. The $i$-th edge connects vertices $A_i$ and $B_i$.

For a positive integer $k$, define a "centipede graph of length $k$" as a graph with $3k$ vertices obtained by the following procedure:

• Prepare a path graph with $k$ vertices.
• For each vertex $v$ of the path graph, add two new vertices adjacent only to $v$.

For example, a centipede graph of length $4$ is as shown in the figure below.

Find the maximum $x$ such that a "centipede graph of length $x$" is contained as a subgraph of tree $T$.

$Q$ test cases are given; solve each of them.

Constraints

• $1 \le Q$
• $3 \le N \le 2 \times 10^5$
• $1 \le A_i, B_i \le N$
• The given graph is a tree.
• The sum of $N$ over all test cases is at most $2 \times 10^5$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

Q
\text{case}_1
\text{case}_2
\vdots
\text{case}_Q

Each test case is given in the following format:

N
A_1 B_1
A_2 B_2
\vdots
A_{N-1} B_{N-1}

Output

Output $Q$ lines.

The $i$-th line should contain the answer for the $i$-th test case.