Given an unrooted tree with $n$ nodes.

Initially, you need to choose a node as the root; subsequently, you can perform any number of operations.

In each operation, you must perform the following steps in order:

• Choose a positive integer $k$.
• Mark every node in the current trees that is at distance $k$ from its root, and remove the edges connecting these nodes to their parents, forming several new trees.
• Let these marked nodes be the roots of the corresponding new trees.

Here, the distance between node $u$ and node $v$ is equal to the number of edges on the simple path between them.

For a pair of nodes $(x, y)$, if there exists a choice of root and a sequence of operations such that nodes $x$ and $y$ are marked in the same operation, we call this pair beautiful.

You need to find the number of beautiful pairs $(x, y)$ such that $1 \le x < y \le n$.

Input

This problem contains multiple test cases.

The first line contains an integer $T$ representing the number of test cases ($1 \le T \le 10^5$).

For each test case:

• The first line contains an integer $n$ ($3 \le n \le 10^6$).
• The next $n-1$ lines each contain two integers $u_i, v_i$, representing an edge connecting nodes $u_i$ and $v_i$.

It is guaranteed that the given edges form a tree, and the sum of $n$ over all test cases does not exceed $10^6$.

Output

For each test case, output a single integer representing the answer.

Examples

Input 1

6
3
2 1
3 2
4
1 2
3 2
2 4
7
7 3
6 5
3 1
1 2
1 5
5 4
9
4 5
5 9
2 8
5 1
3 8
8 9
8 6
6 7
10
3 8
3 2
9 7
4 3
6 1
5 2
3 6
3 7
6 10
10
4 6
3 7
10 8
3 5
2 8
6 10
1 2
5 9
8 9

Output 1

1
3
12
26
28
36

Note

For the first test case, the only beautiful pair is $(1, 3)$.

For the second test case, the beautiful pairs are $(1, 3)$, $(1, 4)$, and $(3, 4)$.