A. DeepTreek
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a tree $$$T$$$ consisting of $$$n$$$ vertices labeled from $$$1$$$ to $$$n$$$, rooted at $$$1$$$. A pair of vertices $$$(u,v)$$$ is called valid if and only if $$$u \ne v$$$, $$$u \ne 1$$$, and $$$u$$$ is not an ancestor$$$^{\text{∗}}$$$ of $$$v$$$.

For a valid pair $$$(u,v)$$$, define $$$f(u,v)$$$ as follows:

  • Consider a new graph $$$T'$$$ obtained by removing the edge between $$$u$$$ and its parent, then adding a new edge between $$$u$$$ and $$$v$$$. It can be proven that $$$T'$$$ is also a tree. $$$f(u,v)$$$ is defined as the depth of $$$T'$$$. Here, the depth of a tree rooted at $$$1$$$ is defined as $$$\max_{1 \le i \le n}d_i$$$, where $$$d_i$$$ is the length of the shortest path between vertices $$$1$$$ and $$$i$$$.

Find the sum of $$$f(u,v)$$$ over all valid pairs $$$(u,v)$$$.

$$$^{\text{∗}}$$$An ancestor of vertex $$$v$$$ is any vertex on the simple path from $$$v$$$ to the root, including the root, but not including $$$v$$$. The root has no ancestors.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$), representing the number of vertices in $$$T$$$.

The $$$i$$$-th of the next $$$n-1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i,v_i \le n$$$, $$$u_i \ne v_i$$$), representing an edge in $$$T$$$. It is guaranteed that the edges form a valid tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output

For each test case, output an integer representing the sum of $$$f(u,v)$$$ over all valid pairs $$$(u,v)$$$.

Example
Input
5
2
1 2
3
1 2
2 3
3
1 2
1 3
6
1 2
2 3
3 4
2 5
5 6
8
1 2
2 3
2 4
4 5
5 6
1 7
7 8
Output
1
5
6
65
163