Given a tree with N nodes and N−1 undirected edges with a constant length of 1, there is a candy shop on each of the nodes. Alex is a candy lover and he wants to try candy from each of the shops. Currently he is standing on node 1 from where he starts his traveling in order to buy candies. He plans to try candies from each shop. He wonders what is the minimum distance he will need to travel in order to be able to buy candies from each shop. Help him find the answer.
Input Format :
Output Format :
For each test case, print the minimum distance Alex will need to travel in order to be able to buy candies from each shop.
Constraints :
1≤T≤10
1≤N≤105
For the first test case:
Alex can get candies from each of the shops by travelling a minimum distance of 6 units.
He does so by travelling in the following order:
For the second test case:
Alex can get candies from each of the shops by travelling a minimum distance of 11 units.
He does so by travelling in the following order: