???题目4 : Agent Communication

描述

In Peking University, there are many homeless cats. The students of cat club built n nests and some paths for those cats. A path connects two nests directly. All nests are connected by paths and there is only one route between any two nests.

Li Lei is the chief of the cat club. He just got some donation for the cats. So he decides to build a new path which connects two nests to make cats travel more easily. He hopes that after the new path is built, the maximum distance between two nests becomes as short as possible. The distance between two nests is defined as the number of paths along the route between two nests.

Can you help Li Lei to figure out how to build the new path?

输入

The first line of input contains an integer t(t ≤ 50), the number of test cases. Then t test cases follow.

For each case:

The first line of input contains an integer n(n ≤ 1000), the number of nests.

Among the next n-1 lines, each line contains two integer x and y (1 ≤ x, y ≤ n), meaning that there is a path between the x-th nest and the y-th nest.

输出

For each test case, output one integer, the maximum distance of two nests after the new path is built correctly.

样例提示

case 1: build a path between 1 and 5

case 2: build a path between 3 and 5

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

3
3