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 :

• The first line contains a single integer \(T\) denoting the number of test cases, then the test case follows.
• For each case, the first line contains a single integer \(N\), representing the number of nodes in the graph.
• Next \(N-1\) lines follow, containing 2 integers a and b, representing that there is an edge between node a and node b.

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 ≤ 10^5\)