给定一棵 $n$ 个节点的无根树，你可以做如下操作若干次：
- 选择当前树上编号最大或最小的点，删去它和以它为一个端点的所有边，保留任意一个连通块作为操作后的树。
令 $min$ 为树上所有节点编号的最小值，$max$ 为树上所有节点编号的最大值，$size$ 为树上的节点个数，则一棵树的权值为 $min \cdot max \cdot size$。求所有能通过上述操作得到的非空的树的权值和，对 $2^{32}$ 取模。
输入格式
第一行一个正整数 $T(1 \le T \le 10^5)$，表示数据组数。
对于每组数据：
第一行一个正整数 $n(1 \le n \le 10^5)$。
接下来 $n-1$ 行，每行两个正整数 $u,v(1 \le u,v \le n)$，表示树上的一条无向边。保证正确描述了一棵树。
保证对于所有数据，$n$ 的和不超过 $10^5$。
输出格式
对于每组数据，输出一行一个非负整数表示答案对 $2^{32}$ 取模后的结果。
样例输入
6 3 1 2 2 3 3 1 3 2 3 7 2 1 3 1 4 1 5 1 6 5 7 6 6 2 1 3 1 4 1 5 4 6 1 9 2 1 3 2 4 3 5 1 6 4 7 5 8 2 9 3 9 2 1 3 2 4 3 5 4 6 5 7 2 8 3 9 5
样例输出
39 35 528 221 1145 1919
子任务
| 子任务编号 | 特殊性质 | 分值 |
|---|---|---|
| $1$ | $n \le 10$ | $5$ |
| $2$ | $n \le 20$ | $10$ |
| $3$ | $n \le 100$ | $10$ |
| $4$ | $n \le 2000$ | $15$ |
| $5$ | $n \le 3 \times 10^4$ | $15$ |
| $6$ | 给定的树中，每个节点的度数 $\le 2$ | $20$ |
| $7$ | 无 | $25$ |