B. 新手的Zelda

每个测试点时间限制：$1$ 秒

每个测试点内存限制：$256$ 兆字节

给定一棵树。

一次 zelda 操作可以执行如下操作：

• 选择树上的两个顶点 $u$ 和 $v$；
• 将从 $u$ 到 $v$ 的路径上的所有顶点压缩成一个顶点。换句话说，路径 $u$ 到 $v$ 上的所有顶点都会从树中删除，同时新建一个顶点 $w$。之后，所有原本与这条路径上某个顶点相连的顶点 $s$，都会改为与新顶点 $w$ 相连。
• 

对顶点 1 和 5 执行的zelda操作示意图。

要求你求出：最少需要多少次 zelda 操作，才能使整棵树最后只剩下一个顶点。

树是一个连通且无环的无向图。

输入格式

每个输入包含多组测试数据。

第一行包含一个整数 $t$，表示测试数据组数，其中：

$$1 \le t \le 10^4$$

对于每组测试数据：

第一行包含一个整数 $n$，表示树中的顶点个数，其中：

$$2 \le n \le 10^5$$

接下来 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$，表示第 $i$ 条边连接的两个顶点，其中：

$$1 \le u_i, v_i \le n,\quad u_i \ne v_i$$

保证给出的边构成一棵树。

保证所有测试数据中 $n$ 的总和不超过：

$$10^5$$

输出格式

对于每组测试数据，输出一个整数，表示让整棵树只剩下一个顶点所需的最少 zelda 操作次数。

样例输入

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

样例输出

1
3
2
2

说明

在第 $1$ 组测试数据中，只需要对顶点 $2$ 和顶点 $4$ 执行一次 zelda 操作即可。

在第 $2$ 组测试数据中，一种可行方案如下：

• $u=2, v=1$，新产生的顶点记为 $w=10$；
• $u=4, v=9$，新产生的顶点记为 $w=11$；
• $u=8, v=10$。

执行完上述操作后，整棵树只剩下一个顶点。