今天你是一只在人们头顶间跳跃的虱子，试图寻找最适合居住的头发。

你想要探索的房间里坐着的一群人可以表示为一棵大小为 $n$ 的树（无环连通图），其中每个人的头是一个顶点，如果两个头之间的跳跃距离为 $1$，则它们之间存在一条边。

你想要访问房间里每个人的头。为了不引起任何人的怀疑，你决定每个头只访问一次。在开始旅程之前，你将训练你的跳跃技能，这将使你能够进行更长距离的跳跃。如果你花费 $d$ 天来掌握跳跃，你现在就能够在树中跳跃不超过 $d$ 的距离。这里，距离 $\text{dist}(u, v)$ 定义为顶点 $u$ 和 $v$ 之间简单路径上的边数。一个头被视为已访问，当且仅当它是起点或者被直接跳落（降落）在上面。请注意，跳过的头（单次跳跃的起点和终点之间的头）不会被标记为已访问。

你需要训练的最少天数是多少，才能访问所有的头？你可以选择任何你想要的起点。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 2 \cdot 10^5$)。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 10^6$)，表示树的大小。

接下来的 $n - 1$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n, u \neq v$)：表示树中由一条边连接的顶点。

所有测试用例的 $n$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出一行，包含一个整数：表示能够跳遍给定的树所需的最少训练天数。

样例

输入样例 1

4
3
1 2
1 3
5
1 2
1 3
1 4
1 5
7
1 2
1 3
2 4
2 5
3 6
3 7
15
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15

输出样例 1

1
2
2
2

说明

对于第一个测试用例，你可以执行以下跳跃序列：$3 \to 1 \to 2$。每次跳跃的距离为 $1$。

第四个测试用例描述了题目描述中的图。当 $d = 2$ 时，一个有效的跳跃序列为：$8 \to 9 \to 4 \to 2 \to 10 \to 11 \to 5 \to 1 \to 6 \to 12 \to 13 \to 3 \to 15 \to 7 \to 14$。距离分别为：$2, 1, 1, 2, 2, 1, 2, 2, 1, 2, 2, 2, 1, 1$。因此，训练 $2$ 天就足够了。