You are given a tree with N vertices. Every vertex has an unique number from the interval [1, N]. Consider all simple paths on this tree. For every simple path you can write the sequence of numbers taken from consecutive vertices on this path. For every such sequence you can find the Longest Increasing Subsequence. Find the longest of all Longest Increasing Subsequences and print its length.

Input

The size of each input file is not greater than 2 MB.

In the first line of the input there is an integer T (1 ≤ T ≤ 1000) - the number of data sets.

In the first line of each data set there is an integer N (1 ≤ N ≤ 10⁵).

In each of the next N - 1 lines of the data set you can find two integers a and b (1 ≤ a, b ≤ N) meaning that there is an edge connecting vertex with number a and vertex with number b.

Output

For each data set print one number: the length of the longest LIS of all simple paths.

Example

Input:
2
12
3 1
1 4
4 12
12 8
4 5
5 11
5 6
5 2
3 9
9 10
9 7
12
1 8
8 6
8 3
3 12
3 10
3 5
5 4
5 2
1 9
9 11
9 7

Output:
4
5

One of the solutions for the second tree in the example: