I. Find Iron Bundle
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

In last year's GPL, Rowlet was playing around with an AI Duck. It was not the smartest duck then, but since then its intelligence has increased sharply! Rowlet will need to find a proper name for it, but for now, it is called Iron Bundle.

Unfortunately, Iron Bundle is extremely fast, so Rowlet has dispatched Psyduck to find it. Psyduck knows it is at one of the $$$N$$$ metro stations in Medali City (to save costs, there are $$$N - 1$$$ sections of track between two stations) but doesn't know which one. As a result, Psyduck will randomly begin searching at one of the $$$N$$$ stations. Rowlet wants to know what the sum of the shortest paths between all possible starting points of Psyduck and Iron Bundle are.

Rowlet has enlisted the help of the local Archaludon to disable exactly one section of track. Archaludon can also sense Iron Bundle (being a Steel type helps), and will tell Rowlet which side of the disabled track Iron Bundle is on. Then, Rowlet can ensure that Psyduck can always reach Iron Bundle. Notice that this drastically cuts down the number of starting pairs for Psyduck and Iron Bundle.

Input

The first line consists of the number $$$T$$$ ($$$1 \leq T \leq 5*10^4$$$), the number of testcases.

Each test case contains on its first line $$$N$$$ ($$$2 \leq N \leq 2*10^5$$$), the number of stations in Medali City.

The next $$$N - 1$$$ lines contain two integers $$$a_i$$$, $$$b_i$$$ $$$(1 \leq a_i, b_i \leq N, a_i \neq b_i)$$$, representing a section of track.

It is guaranteed that the sum of $$$N$$$ across all test cases does not exceed $$$2*10^5$$$.

Output

For each testcase, output a single line containing the minimum sum of lengths.

Example
Input
3
4
1 2
1 3
3 4
5
1 2
1 3
2 4
2 5
5
1 2
2 3
2 4
2 5
Output
2
5
9
Note

In the first test case, it is optimal to remove the track between $$$1$$$ and $$$3$$$. Then we are left with two groups of interconnected stations $$$(1-2)$$$ and $$$(3-4)$$$, which each have path length sum 1.