D. 树的压缩操作

每次测试的时间限制：$2$ 秒
每次测试的内存限制：$256$ 兆字节

Kagari 正在准备归档一棵树，她知道归档的成本取决于树的直径$^*$。为了降低成本，她的目标是首先尽可能缩小直径。她可以对树执行以下操作：

1. 选择两个顶点 $s$ 和 $t$。设从 $s$ 到 $t$ 的简单路径$^\dagger$ 上的顶点序列为 $v_0, v_1, \dots, v_k$，其中 $v_0 = s$，$v_k = t$。
2. 删除路径上的所有边。即删除边 $(v_0, v_1), (v_1, v_2), \dots, (v_{k-1}, v_k)$。
3. 将顶点 $v_1, v_2, \dots, v_k$ 直接连接到 $v_0$。即添加边 $(v_0, v_1), (v_0, v_2), \dots, (v_0, v_k)$。

可以证明，操作后得到的图仍然是一棵树。

请帮助她求出达成最小直径所需的最少操作次数。

$^*$ 树的直径：树中任意两点之间最长路径的长度。路径长度由路径上的边数衡量。
$^\dagger$ 简单路径：树中连接两个顶点且不重复经过任何顶点的路径。可以证明，树中任意两点之间的简单路径是唯一的。

输入
每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）——树的顶点数。

接下来的 $n-1$ 行描述树的边。每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \ne v$），表示顶点 $u$ 和 $v$ 之间有一条边。保证这些边构成一棵树。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出
对于每个测试用例，输出一个整数——使直径最小所需的最少操作次数。

示例

输入

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

说明

第一个测试用例：
原始树的直径是 $3$。Kagari 可以对 $s = 3$ 和 $t = 4$ 执行一次操作。如下图所示，操作步骤包括：

• 删除边 $(3,1)$、$(1,2)$ 和 $(2,4)$。
• 添加边 $(3,1)$、$(3,2)$ 和 $(3,4)$。

操作后，树的直径减少到 $2$。可以证明 $2$ 是可达到的最小直径。

第二个测试用例：
树的直径是 $1$。可以证明 $1$ 已经是最小直径，因此她可以不进行任何操作。