#415 Moving an Edge

Statement

Statement language

You are given a tree $T$ with $N$ vertices numbered $1,2,\ldots,N$ .

Perform the following operation exactly once to obtain a new tree $T'$ .

Delete one edge of $T$ .
Add one edge whose endpoints belong to different connected components after the deletion.
The added edge must be different from the deleted edge.

For a tree $S$ , let $\operatorname{dist}_S(u,v)$ denote the distance between vertices $u$ and $v$ . Define the between and as the number of unordered vertex pairs satisfying

1\le u<v\le N,\qquad \operatorname{dist}_T(u,v)\ne\operatorname{dist}_{T'}(u,v).

Find the minimum possible amount of change.

Input

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the minimum possible amount of change on one line.

Constraints

$1\le T\le100$ .
$3\le N\le200\,000$ .
$1 \leq u_{i}, v_{i} \leq$ ().

Subtasks

#	Score	Constraints
1	10	The sum of $N$ over all test cases does not exceed $10$ .
2	15	The given tree is a path.
3	20	The sum of $N$ over all test cases does not exceed $2\,000$ .
4	20

Samples

Input

Output