Q11: Tree Diameter

Given a connected, positively weighted, undirected graph, we define the "length" between two nodes as the (weighted) length of the shortest path connecting them. The diameter of a graph is then the longest such length over all pair of nodes. Since the graph is connected, the diameter won't be infinity.

In this problem, we only care about the diameter of unweighted trees (connected, acyclic undirected graph)

submit this problem in the judge as "Q11"

INPUT

There will be multiple test cases. The first line will contain an integer numCase equal to the number of test cases.
For each test case, the first line will contain an integer n representing the number of nodes in the tree (2 <= n <= 50000). The next n-1 lines will contain descriptions of the tree edges in the following format:

a b

which means the there is an edge between node a and b. Nodes are numbered from 0 to n-1.

OUTPUT

For each test case, output the graph diameter on a line.

Sample Input

3
2
0 1
5
0 3
1 2
2 3
4 3
6
0 1
0 2
0 3
0 4
0 5

Sample Output

1
3
2