给定一棵有 $n$ 个顶点的有根树，顶点编号为 $1$ 到 $n$，根节点为 $1$。 顶点 $i$ 有一个自然数权值 $a_i$，且任意两个不同顶点的权值互不相同。 定义 $b_u = \text{MEX}\{x \mid \exists v \in \text{subtree}(u), x = a_v\}$。 遗憾的是，权值 $a_i$ 未知。请找出 $\sum_{i=1}^n b_i$ 的最大可能值。 集合的 MEX（Minimum Excluded value）是指不属于该集合的最小非负整数。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。 对于每个测试用例： 第一行包含一个整数 $n$ ($1 \le n \le 5 \cdot 10^5$)，表示节点数量。 接下来的 $n - 1$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n$)，表示树的一条边 $(u, v)$。 保证输入构成一棵树。

输出格式

对于每个测试用例：输出一行，包含一个整数，表示 $\sum_{i=1}^n b_i$ 的最大可能值。

样例

输入格式 1

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

输出格式 1

8
6
1