E. Tom and Jerry
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an undirected tree consisting of $$$n$$$ vertices. A simple path $$$p$$$ of length $$$k$$$ is defined as a sequence of distinct vertices $$$p_0,p_1,\ldots,p_k$$$ such that there exists an undirected edge between vertices $$$p_i$$$ and $$$p_{i+1}$$$ for every $$$0 \le i \lt k$$$. A simple path is uniquely identified by the unordered pair of its endpoints, $$$(p_0,p_k)$$$. That is, $$$(u,v)$$$ and $$$(v,u)$$$ represent the same simple path.

Tom and Jerry are playing a game on this tree. The players take turns, with Tom going first. In the $$$i$$$-th turn ($$$i \ge 1$$$), the current player chooses a simple path $$$(x_i,y_i)$$$ that satisfies the following conditions:

  • $$$x_i \ne y_i$$$.
  • The path does not share any edges with any of the previously chosen paths.
  • Either $$$x_i$$$ or $$$y_i$$$ belongs to the path chosen in the $$$(i-1)$$$-th turn. Note that this condition only applies when $$$i \ge 2$$$.

The player who is unable to choose a valid path on their turn loses the game.

Assuming both Tom and Jerry play optimally, your task is to compute the total number of distinct simple paths Tom can choose in the first turn such that he can guarantee a win.

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 the tree.

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$), representing an undirected edge between vertices $$$u$$$ and $$$v$$$. 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 total number of distinct simple paths Tom can choose in the first turn such that he can guarantee a win.

Example
Input
5
2
1 2
3
1 2
2 3
5
1 2
2 3
2 4
2 5
5
1 2
2 3
3 4
4 5
7
1 2
2 3
2 4
4 5
5 6
5 7
Output
1
1
6
1
5
Note

In the first test case, the tree consists of only two vertices and a single edge between vertex $$$1$$$ and vertex $$$2$$$. Tom can choose the simple path $$$(1,2)$$$ on his first turn. Since this path consumes the only edge in the tree, Jerry will have no unused edges available to form a valid path on his turn. Thus, Jerry is unable to make a move, and Tom wins the game. There is exactly $$$1$$$ winning path for Tom.

In the third test case, the tree is a star graph with vertex $$$2$$$ at the center, connected to vertices $$$1, 3, 4,$$$ and $$$5$$$. There are $$$10$$$ possible simple paths in total.

One of the winning paths is $$$(1,3)$$$:

  • On his first turn, Tom chooses $$$(1,3)$$$. This path uses edges $$$(1,2)$$$ and $$$(2,3)$$$, and its vertices are $$$\{1, 2, 3\}$$$. The unused edges remaining in the tree are $$$(2,4)$$$ and $$$(2,5)$$$.
  • On Jerry's turn, he must pick an edge-disjoint path with at least one endpoint in Tom's path $$$\{1, 2, 3\}$$$. The only valid paths Jerry can choose are $$$(2,4)$$$ or $$$(2,5)$$$. Jerry cannot choose the path $$$(4,5)$$$ because its endpoints $$$4$$$ and $$$5$$$ do not belong to Tom's path $$$\{1, 2, 3\}$$$.
  • Suppose Jerry chooses $$$(2,4)$$$. His path vertices are now $$$\{2, 4\}$$$.
  • On Tom's next turn, he must pick a path with an endpoint in $$$\{2, 4\}$$$. He can simply choose the last remaining path $$$(2,5)$$$.
  • After this, all edges are exhausted, Jerry has no moves left, and Tom wins.

One of the losing paths is $$$(1,2)$$$:

  • Suppose Tom starts by choosing $$$(1,2)$$$. The vertices on his path are $$$\{1, 2\}$$$, and the remaining edges are $$$(2,3), (2,4),$$$ and $$$(2,5)$$$.
  • Jerry can respond by choosing the path $$$(2,3)$$$. This is valid because the endpoint $$$2$$$ is on Tom's previous path. The vertices of Jerry's path are $$$\{2, 3\}$$$.
  • Tom is now forced to choose an unused path with an endpoint in $$$\{2, 3\}$$$. He must choose either $$$(2,4)$$$ or $$$(2,5)$$$. Let's say he chooses $$$(2,4)$$$.
  • Jerry will then easily choose the final remaining path $$$(2,5)$$$, as its endpoint $$$2$$$ belongs to Tom's previous path $$$\{2, 4\}$$$.
  • All edges are now used. Tom cannot make a move on his turn and loses the game.