Monocarp 有一个树,由 $$$n$$$ 个顶点组成。
他将选择一些顶点 $$$r$$$ 并对从 $$$1$$$ 到 $$$n$$$ 的每个顶点 $$$v$$$ 执行以下操作:
- 设置 $$$d_v$$$ 等于从 $$$v$$$ 到 $$$r$$$ 的距离(最短路径上的边数);
- 颜色$$$v$$$一些颜色。
漂亮的着色满足两个条件:
- 对于每对相同颜色的顶点 $$$(v, u)$$$,存在一条从 $$$v$$$ 到 $$$u$$$ 的路径,该路径仅访问相同颜色的顶点;
- 对于每对相同颜色的顶点 $$$(v, u)$$$, $$$d_v \neq d_u$$$。
请注意,Monocarp 可以选择他想要使用的任意数量的不同颜色。
对于每种使用的颜色,他然后计算该颜色的顶点数。树的成本是这些数字中的最小值。
树的最大成本是多少?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — 树中的顶点数。
接下来的 $$$n-1$$$ 行包含两个整数 $$$v$$$ 和 $$$u$$$ ($$$1 \le v, u \le n$$$) - 边的描述。
给定的边形成一棵树。所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 树的最大可能成本。
示例
输入 #1
4 4 1 2 2 3 3 4 5 1 2 1 3 1 4 1 5 3 1 3 3 2 7 3 2 2 5 7 5 3 1 1 6 1 4
输出 #1
4 1 3 3