Minimum Time to Reach the End Checkpoint

You are given a series of race tracks, each consisting of several checkpoints that are connected by bidirectional paths. Each track is structured as a tree connecting N checkpoints using 2N-2 integers which represent N-1 edges (each given as a pair of connected checkpoints). A runner starts at checkpoint 1 and needs to reach checkpoint N in the shortest possible time. All paths have equal weight, meaning that traversing any edge takes exactly one unit of time.

Your task is to calculate the minimum time required for a runner to travel from checkpoint 1 to checkpoint N on each given track. The solution can be derived directly by recognizing that in any tree structure (since there are no cycles and the graph is connected) the shortest path from checkpoint 1 to checkpoint N is simply $N-1$ (i.e. the number of edges in a path that spans from the first to the last checkpoint).

Note: Even though the list of paths is provided, you may not need to process them due to the inherent structure of the tree. All input trees guarantee that the minimum distance from checkpoint 1 to checkpoint N is exactly $N-1$.

inputFormat

The input is given via stdin and consists of multiple test cases. The first line contains a single integer T representing the number of test cases. Each test case is described as follows:

• The first line of each test case contains an integer N — the number of checkpoints.
• The next line contains 2N-2 space-separated integers which represent the edges of the tree in pairs (u v), showing a path between checkpoints u and v.

outputFormat

For each test case, print on stdout a single integer on a new line, which is the minimum time required to go from checkpoint 1 to checkpoint N. Since each edge takes one unit of time, the answer for each test case is $N-1$.

## sample

1
4
1 2 2 3 3 4

3

</p>