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.

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.

见题面 Input 部分

见题面 Output 部分

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.