Give a list of trees. Each tree is rooted at node 1. For each tree, find the smallest level of a leaf.

Input

• The first line contains an integer T, the number of trees (T ≤ 100).

• For each test case:

  • The first line of each test cases contains a integers n (1 ≤ n ≤ 104) which the number of nodes in the corresponding tree.

  • The next n-1 lines, each contains two integers u and v (1 ≤ u, v ≤ n) representing an edge between node u and node v.

    Output

For each tree, print the smallest level of a leaf.

Example

Input

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

Output

1
2