Artam Clancy

Time Limit: 2 Seconds    Memory Limit: 32768 KB

Game design has changed a lot during the past few years. Nowadays games have many storylines that are executed based on player's choices. This paradigm not only makes the games more interesting but also allows fans to play the game several times and go through all storylines.

Artam is writing the story of a new game. He has developed n levels in total, such that there is only one way to reach each level, and going from one level to the next takes exactly one hour. Also, when you finish a level you cannot go back to that level again without starting the game from level 1. Since this is a new game, the storyline might branch out in some levels.

Now, Artam wants to create a new path (a shortcut) in the storyline, that takes the player from level 1 (start of the game) to some other level. His goal is to minimize the number of hours players spend on going through all levels of the game. Note that going through all levels of the game means starting at level 1 and finishing the game (going to the end of a branch in the storyline), then going back to level one and finishing the game in a different branch (different branchs are different in at least one level) in the storyline, and repeating this process until all possible endgames are reached.

 

What is the minimum time a player can go through all levels with such shortcut?

Input

  The first line contains the number of test cases T.

  For each test, the first line contains an integer n (1≤ n ≤ 2*105), the number of levels in the game. Followed by n-1 lines, each contains two integers u and v (1≤ u, v ≤ n), which means it takes one hour to go from level u to level v or vice versa.

  You cannot reach any level from two different levels, and the sum of all levels in all test cases does not exceed 5*105. Also the maximum time to finish the game once is limited to 3*104.

  Use fast IO functions to read the input.

Output

  For each test case, print a single integer in a line, the minimum number of hours required to go through all levels after adding the shortcut.

Sample Input

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

Sample Output

8
2
Submit

Source: 15th Iran Nationwide Internet Contest