Solve the minimum diameter spanning tree problem for the simple graphs.

For a given list of adjacent vertices of a graph G find the minimum diameter spanning tree T and write down the diameter of this tree diam(T).

Each graph has only one connected component, so there is at least one spanning tree, which connects all the vertices.

Input

t [the number of test graphs]
Graph:
n [1 <= n <= 1000 the number of graph vertices]
i m v₁ v₂ ... v_m [the list of m adjacent vertices to vertex i]

Output

For each test case output:
d [diameter of the minimum diameter spanning tree]

Example

Input:
6

10
1 3 2 3 4
2 3 1 5 7
3 3 1 5 6
4 3 1 6 8
5 3 2 3 9
6 3 3 4 10
7 1 2
8 1 4
9 1 5
10 1 6

10
1 4 4 5 7 9
2 1 8
3 4 4 7 8 10
4 3 1 3 9
5 2 1 9
6 2 8 9
7 4 1 3 8 9
8 5 2 3 6 7 9
9 7 1 4 5 6 7 8 10
10 2 3 9

1
1 0

2
1 1 2
2 1 1

3
1 1 2
2 2 1 3
3 1 2

5
1 2 2 4
2 3 1 3 4
3 1 2
4 3 2 5 1
5 1 4

Output:
5
3
0
1
2
3