F. Folding Game of Ohto Ai
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Ohto Ai has an unrooted tree with $$$N$$$ vertices. Let the current tree be $$$G=(V,E)$$$.

A path in a tree is a sequence of distinct vertices $$$v_1,v_2,\ldots,v_k$$$ such that $$$\{v_i,v_{i+1}\}\in E$$$ for every $$$1\le i \lt k$$$.

A diameter of a tree is a path containing the maximum possible number of vertices.

While $$$|V| \gt 1$$$, Ohto Ai may perform the following fold operation: Choose any diameter $$$d_1,d_2,\ldots,d_k$$$ of the current tree, listed in order from one endpoint to the other.

Define a function $$$f:V\to V$$$ by:

$$$$$$ f(v)= \begin{cases} d_{\min\{i,k-i+1\}}, & \text{if }v=d_i\text{ for some }1\le i\le k\\ v, & \text{otherwise} \end{cases} $$$$$$

The tree after the fold is $$$G'=(V',E')$$$, where:

$$$$$$ \begin{aligned} V'&=\{f(v)\mid v\in V\} \\ E'&= \bigl\{ \{f(u),f(v)\} \mid \{u,v\}\in E,\ f(u)\ne f(v) \bigr\} \end{aligned} $$$$$$

In other words, vertices at symmetric positions on the chosen diameter are merged. Edges whose endpoints are merged into the same vertex disappear, and if multiple edges become edges between the same pair of vertices, only one copy is kept.

It can be shown that $$$G'$$$ is still a tree.

Ohto Ai repeatedly performs fold operations until $$$|V|=1$$$. Find the maximum possible number of operations.

Input

The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 3\times 10^3$$$), denoting the number of test cases.

For each test case, the first line contains an integer $$$N$$$ ($$$1 \leq N \leq 5\times 10^4$$$), denoting the number of vertices in the tree.

The next $$$N-1$$$ lines each contain two integers $$$x,y$$$ ($$$1 \leq x,y \leq N$$$, $$$x\neq y$$$), denoting an edge of the tree.

It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$5\times 10^4$$$.

Output

For each test case, output one line containing an integer: the maximum number of fold operations that can be performed on the tree.

Example
Input
3
1
5
1 2
1 3
1 4
4 5
13
1 2
2 3
3 4
2 5
5 6
5 7
1 8
8 9
9 10
8 11
11 12
11 13
Output
0
3
7
Note

For the first test case, the tree with $$$1$$$ vertex has no fold operation that can be performed, so the answer is $$$0$$$.

For the second test case, one optimal folding sequence is shown below:

For the third test case, it can be proven that at most $$$7$$$ fold operations can be performed, so the answer is $$$7$$$.