两只饥饿的小熊猫,Oscar 和 Lura,有一棵树 $$$T$$$,有 $$$n$$$ 节点。他们愿意对整棵树 $$$T$$$ 执行一次以下的洗牌过程。通过这个洗牌过程,他们将从旧树的节点中创建一棵新树。
1. 从原始树$$$T$$$中选择任意节点$$$V$$$。创建一棵新树 $$$T_2$$$,以 $$$V$$$ 作为根。
2. 从$$$T$$$中删除$$$V$$$,使得原始树被分成一棵或多棵子树(或者零个子树,如果$$$V$$$是$$$T$$$中的唯一节点)。
3. 使用相同的过程对每个子树进行打乱(再次选择任意节点作为根),然后将所有打乱后的子树的根连接回 $$$V$$$ 以完成构造 $$$T_2$$$。
此后,奥斯卡和卢拉留下了一棵新树$$$T_2$$$。它们只能吃叶子,而且非常饥饿,所以请找出所有树上一次洗牌中可以产生的叶子的最大数量。
请注意,叶子是度数为 $$$1$$$ 的所有节点。因此,如果根只有一个子节点,则可以将其视为叶子。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) - 原始树 $$$T$$$ 中的节点数。
接下来的 $$$n - 1$$$ 行每行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \leq u, v \leq n$$$) - 原始树 $$$T$$$ 中的一条边。给定的边形成一棵树。
所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数——整棵树上通过一次洗牌过程可实现的最大叶数。
示例
输入 #1
4 5 1 2 1 3 2 4 2 5 5 1 2 2 3 3 4 4 5 6 1 2 1 3 1 4 1 5 1 6 10 9 3 8 1 10 6 8 5 7 8 4 6 1 3 10 1 2 7
输出 #1
4 3 5 6
注意
在第一个测试用例中,可以看出叶子的最大数量是$$$4$$$。为了实现这一点,我们可以选择节点 $$$3$$$ 作为新的根来开始洗牌。
在我们的第二个测试用例中,我们有一行五个节点。可以看出,一次洗牌后叶子的最大数量为$$$3$$$。我们可以从节点 $$$2$$$ 开始,这迫使节点 $$$1$$$ 成为叶子。然后,如果我们选择右侧的节点 $$$4$$$,我们还将有节点 $$$3$$$ 和 $$$5$$$ 作为叶子。
第三个测试用例是具有六个节点的星形图。叶子的数量不能增加,因此我们的答案将是$$$5$$$(如果我们从原始根节点开始洗牌)。