JAG 是 BEST 公司推出的一款革命性新游戏。在这个游戏中，玩家要进行 $T$ 轮比赛，每一轮他们都会拥有一张包含 $N$ 个领土的地图。恰好有 $N - 1$ 对领土拥有公共边界。这张地图是连通的，也就是说，对于任意两个领土 $u$ 和 $v$，你都可以通过穿过其他一些领土从 $u$ 走到 $v$。玩家轮流选择领土，直到所有领土都被选完。游戏有两条规则：

• 不能跳过回合。
• 玩家不能选择已经被自己或对方选过的领土。

我们定义两个领土 $u$ 和 $v$ 之间的距离为从 $u$ 到 $v$ 的路径上需要穿过的最少边界数量。先手的目标是最小化他所选领土中距离最远的两个领土之间的距离。后手的目标是最大化该距离。如果双方都采取最优策略，请输出先手所选领土中距离最远的两个领土之间的距离。

输入格式

输入的第一行包含轮数 $T$。接下来是 $T$ 轮比赛的描述。

对于每一轮，第一行包含一个数字 $N$ ($3 \le N \le 10^5$)，表示领土的数量。接下来的 $N - 1$ 行，每行包含两个数字 $u$ 和 $v$，表示一对拥有公共边界的领土。保证可以从任意领土通过穿过一些边界到达其他任何领土。

保证所有轮次的 $N$ 之和不超过 $200000$。

输出格式

输出 $T$ 行，第 $i$ 行表示如果双方都采取最优策略，先手所选领土中距离最远的两个领土之间的距离。

样例

样例输入 1

1
5
1 2
1 3
1 4
1 5

样例输出 1

2