We are quite aware of the power cuts in BIT.
Boys of Hostel-1 are getting very bored without playing Counter Strike.
They are sitting in upper lawn, but all they can think about is placements.
Bhatia decides to play a game. Actually he is thinking of a code and wants to figure out the test cases.
He made the boys stand in a tree structure, giving them numbers from 1 to N.
Now each boy in his turn will select a boy and will walk on the path connecting the two.
On his way, he gives a hi5 to every boy he meets in his path and then goes back to his place directly.
The boy who gives maximum number of hi5 on his path wins the game.
Help Bhatia get the count of hi5s the winner gave on his path.
Known Fact : Everyone wants to win.

INPUT
The first line of input will contain the number of test cases,T. Each test case will have an integer N followed by some paths that connect them all.

OUTPUT
For each test case print the number of hi5s the winner gave on his path.

CONSTRAINT
0 < T <= 20
1 < N <= 100000

Sample Input
``` 1 5 1 2 1 3 3 4 3 5 ```

Sample Output
``` 3 ```

Problem Setter : Sunny Lalwani
Problem Tester : Rahul Prakash

Languages: Brain,C,C++,Java,Pascal,Perl,PHP,Python,Ruby,Text

Time Limit: 1 Second(s)
Score: 0 Point(s)
Input File Limit: 50000 Bytes

Mode Judge

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0