E. 洗牌

• 时间限制：每个测试点 $2$ 秒
• 内存限制：每个测试点 $256$ 兆字节

两只饥饿的小熊猫 Oscar 和 Lura 有一棵 $n$ 个节点的树 $T$。他们希望恰好一次地对整棵树 $T$ 执行下述洗牌过程。通过该洗牌过程，他们将用原树中的节点创建一棵新树。

1. 从原树 $T$ 中选择任意一个节点 $V$。
2. 创建一棵新树 $T_2$，以 $V$ 为根。
3. 从 $T$ 中删除 $V$，这样原树会分裂成一个或多个子树（若 $V$ 是 $T$ 中唯一的节点，则分裂出零个子树）。
4. 对每个子树递归地执行相同的洗牌过程（同样地，每个子树可任意选择一个节点作为根），然后将所有洗牌后的子树的根连接到 $V$ 上，从而完成 $T_2$ 的构建。

洗牌结束后，Oscar 和 Lura 得到一棵新树 $T_2$。他们只能吃叶子，而且非常饿，所以请找出所有可以通过恰好一次洗牌得到的树中，叶子数的最大值。

注意：叶子定义为度数为 $1$ 的节点。因此，如果根只有一个孩子，它也可以被视为叶子。

输入

第一行包含一个整数 $t$（$1 \le t \le 10^4$）——测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \times 10^5$），表示原树 $T$ 的节点数。

接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$），表示原树 $T$ 中的一条边。给定的边形成一棵树。

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

输出

对于每个测试用例，输出一个整数 —— 在恰好一次洗牌后能得到的树中，叶子数的最大值。

示例

输入

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

输出

4
3
5
6

注

在第一个测试用例中，可以证明最大叶子数为 $4$。为实现该结果，我们可以选择节点 $3$ 作为洗牌的起始根。

接着只剩下一个子树，在该子树中选择节点 $2$ 作为其新根。 这将使得其余 $3$ 个节点都成为叶子，然后将洗牌后的子树连接回新树的根。最终得到的树有 $4$ 片叶子（包括根），其形状如下：

在第二个测试用例中，树是一条长度为 $5$ 的链。可以证明一次洗牌后最多能得到 $3$ 片叶子。我们可以选择节点 $2$ 开始，这使得节点 $1$ 成为叶子。然后在右侧子树中选择节点 $4$，节点 $3$ 和 $5$ 也会成为叶子。

第三个测试用例是一个有 $6$ 个节点的星形图。叶子数无法增加，因此答案为 $5$（如果我们从原始根节点开始洗牌）。