Explorer Bo

Problem Description

Explorer Bo likes exploring mazes around the world.Now he wants to explore a new maze. The maze has $N$ rooms connected with $N-1$ roads of length $1$ so that the maze looks like a tree. Explorer Bo can transfer to a room immediately or walk along a road which is not the one he walked just now. Because the transfer costs too much, Mr Bo will minimum the transfer using times firstly. Mr Bo wants to walk along all the roads at least once,but he is lazy and he wants to minimum the total length he walked. Please help him! Initial point can be arbitrarily selected

Input

The first line of input contains only one integer $T(=20)$, the number of test cases. For each case, the first line contains $1$ integers, $N( \leq 100000)$ as described before. The following $N-1$ lines describe the path. Each line has $2$ integers, $X,Y(1<=X, Y<=N)$,that there is a road between $X$ and $Y$.

Output

Each output should occupy one line.For each case, just output the minimum length to explore all roads.

Sample Input

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

Sample Output

2
8

Author

绍兴一中

Source

2016 Multi-University Training Contest 3