Problem Description

My life of sinking to the bottom, a prodigal and the clouds

Like a shallow-experienced migratory bird, lingering on the riverbank

It is the whispering wind and rain outside, the jungle is whispering:

Upon finding her, one finds spring

Therefore, the clouds cover the sun, and the sylvas become a poem

Spring is here, and Paper wants to preserve a tree. She knows that the cost of storage depends on the diameter of the tree^[1]. To reduce storage space and ensure that the branches do not break, her goal is to first minimize the diameter as much as possible. She can perform the following operations on the tree:

• Choose two vertices $s$ and $t$, and let the sequence of vertices on the simple path^[2] from $s$ to $t$ be $v_0, v_1, \dots, v_k$, where $v_0 = s$ and $v_k = t$;
• Remove all edges on the path; in other words, remove edges $(v_0, v_1), (v_1, v_2), \dots, (v_{k-1}, v_k)$;
• Connect vertices $v_1, v_2, \dots, v_k$ directly to $v_0$, in other words, add edges $(v_0, v_1), (v_0, v_2), \dots, (v_0, v_k)$.

It can be proven that after the aforementioned operations, the graph remains a tree. Please assist her in determining the minimum number of operations required to achieve the minimum diameter.

Input

Each test case consists of multiple test cases, and the first line contains the number of test cases $t$ ($1 \leqslant t \leqslant 10^4$); the description of the test cases is as follows:

The first line of each test case contains an integer $n$ ($2 \leqslant n \leqslant 2 \times 10^5$) indicating the number of nodes in the tree.

For each test case, the following $n-1$ lines describe a tree: each line contains two integers $u$ and $v$ ($1 \leqslant u, v \leqslant n$, $u \neq v$) representing an edge between vertices $u$ and $v$, ensuring that these edges form a tree.

Ensure that the sum of $n$ for all test cases does not exceed $2 \times 10^5$.

Output

For each test case, output an integer representing the minimum number of operations to minimize the diameter.

Samples

4
4
1 2
1 3
2 4
2
2 1
4
1 2
2 3
2 4
11
1 2
1 3
2 4
3 5
3 8
5 6
5 7
7 9
7 10
5 11

1
0
0
4

Note

In the first test case, the diameter of the original tree is 3. Paper can perform operations on $s = 1$ and $t = 4$. As shown in the figure, the operation involves the following steps:

1. Remove the edges $(1, 2)$, $(2, 3)$ and $(3, 4)$ from the tree
2. Add tree edges $(1, 2)$, $(1, 3)$ and $(1, 4)$

After the aforementioned operations, the diameter is reduced to $3$. It can be proven that $3$ is the minimum diameter.

In the second example, the diameter of the tree is 1. It can be proven that 1 is already the minimum value, so Paper does not need to perform any operation.