#585 All Falls Down

Statement

Statement language

Alice and Bob are playing All Falls Down, a game in which two tokens fall down a tree. The board is a tree rooted at vertex $1$ , with each child placed below its parent.

First, Alice chooses two distinct vertices $u,v$ and places one token on each vertex.

Starting with Bob, the players then take turns. On a turn, the player must choose one child of the current vertex for each token and move both tokens simultaneously to the chosen children. In other words, both tokens must fall one level down. If either token cannot move farther down, the player whose turn it is loses.

Both players play optimally. Count the unordered pairs $\{u,v\}$ of distinct vertices for which Alice wins.

Input

The input is given in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each case, print the number of vertex pairs for which Alice wins on its own line.

Constraints

$1\leq T\leq200\,000$ .
$1\leq N\leq200\,000$ .
$1 \leq_{}$ ().

Subtasks

#	Score	Constraints
1	10	$N\leq8$ , and the sum of $N$ over all cases is at most $2000$ .
2	25	$N\leq2000$ , and the sum of over all cases is at most .

Samples

Input

Output

In the first case, there is only one vertex, so no pair of distinct vertices can be chosen. The answer is $0$ .
In the second case, the only pair for which Alice wins is $\{1,2\}$ . The token at vertex $2$ cannot move down, so Bob loses on his first turn.
In the third case, the pairs for which Alice wins are $\{1,3\}$ and . Both pairs contain vertex , so Bob loses on his first turn. For the remaining pair , Bob moves the tokens to vertices and , respectively, and Alice loses on her next turn.