Given an unrooted tree with $n$ nodes, you can perform the following operation any number of times:

• Choose the node with the smallest or largest index currently in the tree, remove it and all edges incident to it, and keep any one of the resulting connected components as the tree for the next step.

Let $min$ be the minimum index of all nodes in the tree, $max$ be the maximum index of all nodes in the tree, and $size$ be the number of nodes in the tree. The weight of a tree is defined as $min \cdot max \cdot size$. Calculate the sum of the weights of all possible non-empty trees that can be obtained through the above operations, modulo $2^{32}$.

Input

The first line contains a positive integer $T(1 \le T \le 10^5)$, representing the number of test cases.

For each test case:

The first line contains a positive integer $n(1 \le n \le 10^5)$.

The next $n-1$ lines each contain two positive integers $u, v(1 \le u, v \le n)$, representing an undirected edge in the tree. It is guaranteed that the input describes a valid tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case, output a single non-negative integer representing the answer modulo $2^{32}$.

Examples

Input 1

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

Output 1

39
35
528
221
1145
1919

Subtasks