假设您有 $$$k$$$ 一维线段 $$$s_1, s_2, \dots s_k$$$ (每个线段由两个整数表示 - 它的端点)。然后您可以在这些段上构建以下图表。该图由 $$$k$$$ 个顶点组成,当且仅当线段 $$$s_i$$$ 和 $$$s_j$$$ 相交(存在至少一个属于它们两者的点)时,第 $$$i$$$ 和第 $$$j$$$ 顶点之间存在一条边 ($$$i \neq j$$$)。
例如,如果 $$$s_1 = [1, 6]、s_2 = [8, 20]、s_3 = [4, 10]、s_4 = [2, 13]、s_5 = [17, 18]$$$,则结果图如下:
如果可以选择 $$$m$$$ 一维线段,使得在这些线段上构建的图与该树一致,则大小为 $$$m$$$ 的树是好的。
给你一棵树,你必须找到其最大可能大小的好子树。回想一下,子树是树的连通子图。
请注意,您必须回答 $$$q$$$ 独立查询。
输入
第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 15 \cdot 10^4$$$) — 查询的数量。
每个查询的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — 树中的顶点数。
接下来的 $$$n - 1$$$ 行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \le x, y \le n$$$) 表示顶点 $$$x$$$ 和 $$$y$$$ 之间的边。保证给定的图是一棵树。
保证所有$$$n$$$的总和不超过$$$3 \cdot 10^5$$$。
输出
对于每个查询,打印一个整数 — 给定树的好子树的最大大小。
示例
输入 #1
1 10 1 2 1 3 1 4 2 5 2 6 3 7 3 8 4 9 4 10
输出 #1
8
注意
在第一个查询中,有一个大小为 $$$8$$$ 的良好子树。属于该子树的顶点是$$${9, 4, 10, 2, 5, 1, 6, 3}$$$。