说明

gsy 最近玩了一个很有趣的寻宝游戏，这个游戏有一个 AI，会根据玩家的习惯来调整游戏难度，保证玩家能够通关游戏，但是又不会很容易通关游戏

这是一个有 n 个房间的迷宫编号分别为 1,2,3...n，有 n - 1 条道路将这 n 个房间连通，每条道路的长度为 1，保证从任意一个房间出发可以到达所有房间。

gsy 手里有一个 `宝藏探测器` ，是整个游戏中最重要的道具。

这个 `宝藏探测器` 可以有一个探测范围 x，表示所有跟所在房间距离小于等于 x 的房间都可以被探测到。

当游戏开始时所有房间都会出现一个宝箱，而 gsy 会出现在编号为 1 的房间中。

gsy 的游戏策略非常简单，她每次会在 `宝藏探测器` 中找到离她最近的宝藏所在房间，并且走过去，如果有多个这样的房间就随便挑一个。

但是如果 gsy 在探测器中找不到任何有宝箱的房间了，那她就不知道该怎么办，就会迷失在游戏中。

当 gsy 拿到总共 n 个宝箱以后，不论她身处何处，在 1 号房间会刷新一个终极宝箱，拿到这个宝箱就可以通关游戏。

现在由你来设计这个游戏 AI，给 gsy 设置 `宝藏探测器` 的探测范围，使得 gsy 有通关游戏的可能，但是为了游戏不那么简单，所以探测范围越小越好
 

输入格式

输入第一行为一个正整数 T 表示有多少组测试数据

对于每组测试数据满足：
1. 输入第一行包含一个正整数 n 表示地图中有多少个房间

2. 接下来 n - 1 行每行包含两个整数 x,y 表示 x 和 y 这两个房间之间存在一条道路

对于 30% 的数据，T <= 5, 2 <= n <= 10

对于 60% 的数据，T <= 10, 2 <= n <= 10000

对于 100% 的数据，T <= 1000, 2 <= n <= 2 * 10^5

特别的，对于所有数据满足 sum{n} <= 2 * 10^5，1 <= x,y <= n, x neq y

输出格式

输出一行包含一个整数，表示最小的探测范围 x

样例

2
3
1 2
1 3
7
1 2
2 3
3 4
1 5
5 6
5 7

2
3

提示

对于第 2 组测试数据

最小的探测范围是 3 可以使得 gsy 有机会通关游戏

其中一条路线为 1->5->6->7->2->3->4->1