Problem Description

You are given a rooted tree consisting of $n$ vertices numbered from $1$ to $n$, and the root is vertex $1$.

Vertex $i$ has a natural number weight $a_i$, and $\textbf{no two different vertexes have the same weight}$.

Define $b_u = MEX$ { $x \space | \space \exists v \in subtree\left( u \right), x = a_v\$}.

Unfortunately, $a_i$ are not given. Please find out the maximum possible $\sum_{i=1}^{n}b_i$.

The $\textbf{MEX}$ of a set is the minimum non-negative integer that doesn't belong to the set.

Input

The first line contains one integer $T \left( 1 \leq T \leq 10 \right)$, indicating the number of test cases.

For each test case:

The first line contains one integer $n \left( 1 \le n \le 5 \cdot 10^5 \right)$, indicating the number of nodes.

In the following $n-1$ lines, each line contains two interger $u, v \left(1 \le u, v \le n \right)$, indicating an edge $\left( u, v \right)$ of the tree.

A guarantee is that forming trees.

Output

For each test case:
One line with an integer, indicating the maximum possible $\sum_{i=1}^{n}b_i$.

3
5
1 2
3 2
1 5
4 1
3
1 2
2 3
1

8
6
1