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.
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.
For each test case print the number of hi5s the winner gave on his path.
0 < T <= 20
1 < N <= 100000
Problem Setter : Sunny Lalwani
Problem Tester : Rahul Prakash