E. Moshkeltak kbeereh kteeeeer lek Moooooon
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Moon had the worst breakup ever, again. His ex was way smarter than him, which devastated him. So, he needed advice from the one and only Apple, again. Apple decided to take Moon to Abu Shehab for help.

Moon said, "4 JAYYED."

Apple introduced Moon to Abu Shehab, and as Moon began to open up, Abu Shehab sighed and said, "moshkeltak kbeereh kteeeeer lek Moooooon"

Abu Shehab gave Moon a map of Haret Al-Dabe3. The map looks like a tree with $$$n$$$ nodes, where the nodes are numbered from $$$0$$$ to $$$n-1$$$.

A tree is a connected graph without cycles, where there is a unique path between any two nodes.

Abu Shehab told Moon that he should choose two nodes, $$$x$$$ and $$$y$$$, in the tree and walk along the path from $$$x$$$ to $$$y$$$. To forget his ex, he should choose the two nodes so that the $$$\operatorname{MEX}$$$ of the indices of the nodes on the path is as large as possible.

Can you help Moon solve this problem?

Note: The $$$\operatorname{MEX}$$$ (Minimum EXcluded value) of an array is the smallest non-negative integer that is not in the array. For example:

  • The $$$\operatorname{MEX}$$$ of $$$[1, 2, 3]$$$ is $$$0$$$
  • The $$$\operatorname{MEX}$$$ of $$$[0, 1, 2]$$$ is $$$3$$$
  • The $$$\operatorname{MEX}$$$ of $$$[0, 1, 3]$$$ is $$$2$$$
Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases. Each test case consists of two lines:

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5 $$$), — denotes the number of nodes.

Then the input will contain $$$n-1$$$ lines, each line will contain two integers $$$u$$$ and $$$v$$$ $$$(0 \leq u \leq n - 1)$$$ $$$(0 \leq v \leq n - 1)$$$, which means that there is an undirected edge between nodes $$$u$$$ and $$$v$$$.

The sum of the values of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, print the maximum $$$\operatorname{MEX}$$$ of the set of nodes for a path in the tree.

Example
Input
3
4
0 1
0 2
0 3
4
0 1
1 2
2 3
6
0 4
4 2
0 1
4 3
4 5
Output
3
4
3
Note

Abu Shehab shekleen ma be7kee.

In the third example Moon should choose the path between nodes $$$1$$$ and $$$2$$$: