题面描述

我沉底的一生、浪子与云霞

如阅历浅浅的游鸟，耽于河岸

是呢喃的风雨外，密林耳语：

寻见她，便寻见春日

是故层云蔽日，万木成诗

春天来了，Paper 想要把一棵树保存起来，她知道存储的成本取决于树的直径^[1]。为了降低存储空间保证不折断枝条，她的目标是首先尽可能地缩小直径，可以对这棵树执行以下操作：

• 选取两个顶点 $s$ 和 $t$，设从 $s$ 到 $t$ 的简单路径^[2]上的顶点序列为 $v_0, v_1, \dots, v_k$，其中 $v_0 = s$，$v_k = t$；
• 移除路径上的所有边；换句话说，移除边 $(v_0, v_1), (v_1, v_2), \dots, (v_{k-1}, v_k)$；
• 将顶点 $v_1, v_2, \dots, v_k$ 直接连接到 $v_0$，换句话说，添加边 $(v_0, v_1), (v_0, v_2), \dots, (v_0, v_k)$。

可以证明，经过上述操作后，该图仍然是一棵树，请帮助她确定实现最小直径所需的最少操作次数。

输入描述

每个测试包含多个测试用例，第一行包含测试用例的数量 $t$（$1 \leqslant t \leqslant 10^4$）；测试用例的描述如下：

每个测试用例的第一行包含一个整数 $n$（$2 \leqslant n \leqslant 2 \times 10^5$）表示树中结点的数量。

每个测试用例接下来的 $n-1$ 行描述了一棵树：每行包含两个整数 $u$ 和 $v$（$1 \leqslant u, v \leqslant n$，$u \neq v$），表示顶点 $u$ 和 $v$ 之间的边并保证这些边构成一棵树。

保证所有测试用例的 $n$ 之和不超过 $2 \times 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。Paper 可以对 $s = 1$ 和 $t = 4$ 执行操作。如图所示，该运算包含以下步骤：

1. 移除树径 $(1, 2)$，$(2, 3)$ 和 $(3, 4)$。
2. 添加树径 $(1, 2)$，$(1, 3)$ 和 $(1, 4)$。

经过上述操作，直径减小为 $3$。可以证明 $3$ 是最小直径。

在第二个样例中，树的直径为 1。可以证明 1 已经是最小值，因此 Paper 无需执行任何操作。