C. 树剪枝

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

t+pazolite, ginkiha, Hommarju - Paved Garden

你有一棵有 $n$ 个节点的树，根节点为 $1$。
本题中，叶子 的定义是：非根节点且度数为 $1$ 的节点。

在一次操作中，你可以移除一个叶子及其相连的边（移除后，可能会出现新的叶子）。
请问：最少需要多少次操作，才能得到一棵仍然以 $1$ 为根的树，且这棵树的所有叶子到根的距离都相等？

输入格式

每个测试点包含多个测试用例。
第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。
接下来每个测试用例的格式如下：

• 第一行包含一个整数 $n$（$3 \le n \le 5 \cdot 10^5$），表示节点数。
• 接下来 $n-1$ 行，每行两个整数 $u, v$（$1 \le u, v \le n$，$u \ne v$），表示一条连接 $u$ 和 $v$ 的边。
  输入保证这些边构成一棵树。

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

输出格式

对于每个测试用例，输出一个整数：达到目标所需的最少操作次数。

样例

输入：

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

输出：

2
2
5

样例解释

在前两个样例中，树的形状如下：

• 第一个样例：通过删除边 $(1,3)$ 和 $(2,5)$，得到的树的所有叶子（节点 $6$ 和 $7$）到根（节点 $1$）的距离相等，均为 $3$。答案为 $2$，这是实现目标所需的最少删除边数。
• 第二个样例：删除边 $(1,4)$ 和 $(5,7)$ 后，得到的树的所有叶子（节点 $4$ 和 $5$）到根（节点 $1$）的距离相等，均为 $2$。