给定一棵 $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

子任务