Description

庭中有奇树，绿叶发华滋。攀条折其荣，将以遗所思。—— 《古诗十九首》

树的定义对部分同学来说或许太过抽象。换个说法吧：一棵树可想做是由一个点开始，藉由许多条边不断地延伸拓展到其他点，而且点和边都不会重复地被拓展到。

Node——「节点」。进行延伸拓展的点、被延伸拓展到的点，称作「节点」，也就是说树上的点都是「节点」。

【注：为了方便，以下仍称呼「点」。 】

Branch——「枝」。延伸拓展所用到的边称作「枝」，也就是说树上的边都是「枝」。一个点藉由边往外延伸拓展，称做「分枝（ Branching ）」。

【注：为了方便，以下仍称呼「边」。 】

Root——「根」。方才提到，一棵树可想做是由一个点开始分枝──这个点便是「根」。一棵树上的每一个点都可以做为根。

Leaf——「叶」。在一棵树上选定根后，由根开始不断分枝，途中所有无法继续分枝的点皆是「叶」。

另一种说法是：除了根以外，只连着一条边的点就是叶。但这种说法有个例外：如果树上总共只有一个点，那么此点既是根、也是叶。

树的特性

1. 树没有环。

2. 任意两点之间只有唯一一条路径。

3. 树上所有点之间都相连通。

4. 在树上任意添加一条边，就会产生环。

5. 在树上任意删除一条边，一颗树就裂成两棵树。

6. 边数等于点数减一。

MatRush耐心地讲解完树的基础知识后，请你帮忙他求一下，从任意一个叶子走到另一个叶子，至多需要多少步？

Input

输入的第一行包含一个整数 T，表示测试数据的组数。每组数据首先一行包含一棵树的结点个数N(1 <= N <= 1000)，接下来有N-1行，每行包含两个数x, y(1 <= x,y <= N)，表示x和y之间有一条边。数据保证所构成的是一棵树。

Output

对于每组数据，输出一行，即所求的步数。

Sample

Input

1
5
1 2
2 3
2 4
4 5

Output

3

Hint

步数即所经过边数

Source: MatRush