D. Black, Gray and White
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a tree with $$$n$$$ vertices, numbered from $$$1$$$ to $$$n$$$. Initially, all vertices are white.

You must choose a single integer $$$k$$$ from $$$1$$$ to $$$2n$$$, inclusive. Then, for each $$$i$$$ from $$$1$$$ to $$$n$$$ in increasing order, if the tree contains a vertex numbered $$$k-i$$$ and $$$k-i \ne i$$$, the following operation is performed:

  1. vertices $$$i$$$ and $$$k-i$$$ are recolored black, regardless of their current colors;
  2. all white vertices on the simple path between $$$i$$$ and $$$k-i$$$ are recolored gray. The colors of the other vertices on this path do not change.

You must choose $$$k$$$ to maximize the number of black vertices (higher priority) and the number of gray vertices (lower priority). In other words, choose $$$k$$$ so that the number of black vertices in the tree is as large as possible, and among the values of $$$k$$$ that give the maximum number of black vertices, choose one that gives as many gray vertices as possible.

Find any optimal value of $$$k$$$. If there are multiple suitable values of $$$k$$$, print any of them.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 3 \cdot 10^5$$$) — the number of vertices in the tree.

Each of the following $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$) — the vertices connected by an edge.

Additional constraints on the input:

  • the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$;
  • in each test case, the edges form a tree.
Output

For each test case, print one integer $$$k$$$ ($$$1 \le k \le 2n$$$) that satisfies the requirements of the problem. If there are multiple optimal values, output any of them.

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

In the first test case, $$$k=6$$$ is chosen. After all operations, vertices $$$1$$$, $$$2$$$, $$$4$$$, and $$$5$$$ are black, and vertex $$$3$$$ is gray.

In the second test case, $$$k=7$$$ is chosen. After all operations, all six vertices are black, and there are no gray vertices.