E. Resourceful Caterpillar Sequence
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
Endless Repeating 7 Days
— r-906, Panopticon

There is a tree consisting of $$$n$$$ vertices. Let a caterpillar be denoted by an integer pair $$$(p, q)$$$ ($$$1 \leq p, q \leq n$$$, $$$p \neq q$$$): its head is at vertex $$$p$$$, its tail is at vertex $$$q$$$, and it dominates all the vertices on the simple path from $$$p$$$ to $$$q$$$ (including $$$p$$$ and $$$q$$$). The caterpillar sequence of $$$(p, q)$$$ is defined as the sequence consisting only of the vertices on the simple path, sorted in the ascending order of the distance to $$$p$$$.

Nora and Aron are taking turns moving the caterpillar, with Nora going first. Both players will be using his or her own optimal strategy:

  • They will play to make himself or herself win;
  • However, if it is impossible, they will play to prevent the other person from winning (thus, the game will end in a tie).

In Nora's turn, she must choose a vertex $$$u$$$ adjacent to vertex $$$p$$$, which is not dominated by the caterpillar, and move all the vertices in it by one edge towards vertex $$$u$$$$$$^{\text{∗}}$$$. In Aron's turn, he must choose a vertex $$$v$$$ adjacent to vertex $$$q$$$, which is not dominated by the caterpillar, and move all the vertices in it by one edge towards vertex $$$v$$$. Note that the moves allowed to the two players are different.

Whenever $$$p$$$ is a leaf$$$^{\text{†}}$$$, Nora wins$$$^{\text{‡}}$$$. Whenever $$$q$$$ is a leaf, Aron wins. If either initially both $$$p$$$ and $$$q$$$ are leaves, or after $$$10^{100}$$$ turns the game has not ended, the result is a tie.

Please count the number of integer pairs $$$(p, q)$$$ with $$$1 \leq p, q \leq n$$$ and $$$p \neq q$$$ such that, if the caterpillar is initially $$$(p, q)$$$, Aron wins the game.

$$$^{\text{∗}}$$$In other words: Let the current caterpillar sequence be $$$c_1, c_2, \ldots, c_k$$$, then after the move, the new caterpillar sequence becomes $$$d(u, c_1), d(u, c_2), \ldots, d(u, c_k)$$$. Here, $$$d(x, y)$$$ is the next vertex on the simple path from $$$y$$$ to $$$x$$$.

$$$^{\text{†}}$$$In a tree, a vertex is called a leaf if and only if its degree is $$$1$$$.

$$$^{\text{‡}}$$$Therefore, Nora never fails to choose a vertex $$$u$$$ when the game has not ended. The same goes for Aron.

Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2\cdot 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 2\cdot 10^5$$$) — the number of vertices in the tree.

The following $$$n - 1$$$ lines each contain two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$), denoting an edge between vertices $$$u$$$ and $$$v$$$. It is guaranteed that the given edges form a tree.

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

Output

For each test case, output a single line containing an integer: the number of integer pairs $$$(p, q)$$$ which make Aron win.

Example
Input
5
2
1 2
5
1 2
1 3
2 4
2 5
12
1 6
11 2
4 8
12 3
2 7
6 12
8 1
2 3
5 12
9 2
10 3
10
1 2
2 3
3 4
4 5
5 6
4 7
6 8
4 9
4 10
25
1 16
11 22
6 14
3 1
20 14
23 17
25 19
10 11
3 18
10 6
2 21
4 5
11 12
4 9
9 13
8 6
6 1
3 7
8 19
10 24
15 13
1 2
3 4
17 8
Output
0
6
40
27
171
Note

In the first test case, all possible caterpillars are $$$(1, 2)$$$ and $$$(2, 1)$$$, resulting in a tie at the beginning, since both $$$p$$$ and $$$q$$$ are leaves.

In the second test case, the caterpillars that allow Aron to win are the following: $$$(1, 3)$$$, $$$(1, 4)$$$, $$$(1, 5)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$, $$$(2, 5)$$$. Let's look at some specific caterpillars.

  • For the caterpillar $$$(1, 5)$$$: vertex $$$p = 1$$$ is not a leaf, but vertex $$$q = 5$$$ is, so Aron wins at the beginning.
  • For the caterpillar $$$(2, 1)$$$: vertex $$$p = 2$$$ is not a leaf, neither is vertex $$$q = 1$$$. In Nora's first move, she can choose to move the caterpillar towards vertex $$$5$$$, therefore the caterpillar becomes $$$(5, 2)$$$, and vertex $$$p = 5$$$ is a leaf, so Nora will win.