树是没有循环的连通图。有根树有一个特殊的顶点,称为根。顶点 $$$v$$$ 的父顶点(与根不同)是从根到顶点 $$$v$$$ 的最短路径上 $$$v$$$ 顶点的前一个顶点。顶点 $$$v$$$ 的子节点都是以 $$$v$$$ 为父节点的顶点。
如果一个顶点没有子节点,那么它就是一个叶子。如果满足以下三个条件,我们将顶点称为芽:
- 它不是根,
- 它至少有一个孩子,并且
- 它的所有子节点都是叶子。
给你一棵有 $$$n$$$ 个顶点的有根树。顶点 $$$1$$$ 是根。在一次操作中,您可以选择任何芽及其所有子代(它们是叶子)并将它们重新挂到树的任何其他顶点。通过执行此操作,您可以删除连接芽及其父级的边,并在芽和树的选定顶点之间添加一条边。所选顶点不能是芽本身或其任何子节点。芽的所有子代都与芽保持连接。
如果可以进行任意数量的上述操作(可能为零),则可以获得的最小叶子数量是多少?
输入
输入由多个测试用例组成。第一行包含一个整数 $$$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 \neq v$$$),这意味着树中的顶点 $$$u$$$ 和 $$$v$$$ 之间有一条边。
保证给定的图是一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 经过某些操作后可能获得的叶子的最小数量。
示例
输入 #1
5 7 1 2 1 3 1 4 2 5 2 6 4 7 6 1 2 1 3 2 4 2 5 3 6 2 1 2 7 7 3 1 5 1 3 4 6 4 7 2 1 6 2 1 2 3 4 5 3 4 3 6
输出 #1
2 2 1 2 1
注意
在第一个测试用例中,树如下所示:
首先你可以选择一个芽顶点$$$4$$$并将其重新挂到顶点$$$3$$$。之后,您可以选择一个芽顶点$$$2$$$并将其重新挂到顶点$$$7$$$。结果,您将得到以下带有 $$$2$$$ 叶子的树:
可以证明它是可能得到的最小叶子数。
在第二个测试用例中,树如下所示:
您可以选择一个芽顶点 $$$3$$$ 并将其重新挂到顶点 $$$5$$$。结果,您将得到以下带有 $$$2$$$ 叶子的树:
可以证明它是可能得到的最小叶子数。