Xiao Jian is studying discrete mathematics. Today's topic is graph theory, and he made the following two notes in class:

1. A tree of size $n$ consists of $n$ nodes and $n-1$ undirected edges, such that there is exactly one simple path between any two nodes. Removing a node and its associated edges from a tree splits it into several subtrees; removing an edge (keeping the associated nodes) splits the tree into exactly two subtrees.
2. For a tree of size $n$ and any node $c$ in the tree, $c$ is called a centroid of the tree if and only if, after removing $c$ and its associated edges, the size of every resulting subtree does not exceed $\lfloor \frac{n}{2} \rfloor$ (where $\lfloor x \rfloor$ is the floor function). For a tree containing at least one node, it can have only 1 or 2 centroids.

After class, the teacher gave him a tree $S$ of size $n$, with nodes labeled $1 \sim n$. Xiao Jian's homework is to find the sum of the centroid labels of the two subtrees formed by removing each edge of $S$ individually. That is:

$$\sum_{(u,v) \in E} \left( \sum_{\substack{1 \le x \le n \\ x \text{ is a centroid of } S'_u}} x + \sum_{\substack{1 \le y \le n \\ y \text{ is a centroid of } S'_v}} y \right)$$

In the formula above, $E$ represents the set of edges of tree $S$, and $(u, v)$ represents an edge connecting node $u$ and node $v$. $S'_u$ and $S'_v$ represent the subtrees containing node $u$ and node $v$, respectively, after removing edge $(u, v)$ from tree $S$.

Xiao Jian thinks the homework is not simple, so he asks for your help. Please teach him how to solve it.

Input

The input contains multiple test cases. The first line contains an integer $T$, representing the number of test cases. For each test case: The first line contains an integer $n$, representing the size of tree $S$. The next $n-1$ lines each contain two space-separated integers $u_i, v_i$, representing an edge $(u_i, v_i)$ in the tree.

Output

For each test case, output a single integer on a new line, representing the sum of the centroid labels of the two subtrees formed by removing each edge of the tree individually.

Examples

Input 1

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

Output 1

32
56

Note 1

For the first test case: Removing edge $(1, 2)$, the centroid labels of the subtree containing node 1 are $\{1\}$, and the centroid labels of the subtree containing node 2 are $\{2, 3\}$. Removing edge $(2, 3)$, the centroid labels of the subtree containing node 2 are $\{2\}$, and the centroid labels of the subtree containing node 3 are $\{3, 5\}$. Removing edge $(2, 4)$, the centroid labels of the subtree containing node 2 are $\{2, 3\}$, and the centroid labels of the subtree containing node 4 are $\{4\}$. Removing edge $(3, 5)$, the centroid labels of the subtree containing node 3 are $\{2\}$, and the centroid labels of the subtree containing node 5 are $\{5\}$. Therefore, the answer is $1 + 2 + 3 + 2 + 3 + 5 + 2 + 3 + 4 + 2 + 5 = 32$.

Examples 2-4

See the files centroid/centroid2.in and centroid/centroid2.ans, centroid/centroid3.in and centroid/centroid3.ans, and centroid/centroid4.in and centroid/centroid4.ans in the contestant's directory. Data for examples 3 and 4 satisfy special properties A and B, respectively, as described in the Constraints section.

Constraints

In the "Special Property" column, the two variables are defined by the existence of a permutation $p_i$ of $1 \sim n$ ($1 \le i \le n$), such that: $A$: The tree is a chain. That is, $\forall 1 \le i < n$, there exists an edge $(p_i, p_{i+1})$. $B$: The tree is a perfect binary tree. That is, $\forall 1 \le i \le \frac{n-1}{2}$, there exist two edges $(p_i, p_{2i})$ and $(p_i, p_{2i+1})$. For all test cases: $1 \le T \le 5$, $1 \le u_i, v_i \le n$. It is guaranteed that the given graph is a tree.