B. Binary Search Trees
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Beatrice has a tree $$$T$$$ with $$$n$$$ vertices numbered from $$$1$$$ to $$$n$$$, each of degree at most three. She considers all possible ways to assign the keys $$$1, 2, \ldots, n$$$ to the vertices, with one key per vertex and each key used exactly once. Let $$$k_i$$$ be the key assigned to vertex $$$i$$$.

After assigning the keys, Beatrice can choose a vertex as the root of $$$T$$$ and designate the children of each vertex as left or right. The resulting tree is a binary search tree if the following conditions hold:

  • Each vertex has at most one left child and at most one right child.
  • For every vertex $$$i$$$, if it has a left child, all keys in its left subtree are smaller than $$$k_i$$$. Similarly, if it has a right child, all keys in its right subtree are greater than $$$k_i$$$.

For a fixed assignment of keys, a vertex $$$r$$$ is a valid root if $$$T$$$ can be made into a binary search tree rooted at $$$r$$$ by designating each child as left or right. The search quality of the assignment is the number of valid roots.

For the given tree $$$T$$$, find the sum of the search qualities of all possible assignments, modulo $$$998\,244\,353$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$, denoting the number of vertices ($$$2 \le n \le 2 \cdot 10^5$$$).

Each of the following $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$, denoting the endpoints of an edge ($$$1 \le u, v \le n$$$; $$$u \ne v$$$). The edges form a tree in which every vertex has degree at most three.

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

Output

For each test case, print the sum of the search qualities of all assignments, modulo $$$998\,244\,353$$$.

Example
Input
3
3
1 2
2 3
4
3 2
2 4
1 2
5
1 3
3 5
5 4
5 2
Output
10
12
28
Note

For the first test case, the valid roots for each assignment are:

Keys $$$(k_1,k_2,k_3)$$$$$$(1,2,3)$$$$$$(1,3,2)$$$$$$(2,1,3)$$$$$$(2,3,1)$$$$$$(3,1,2)$$$$$$(3,2,1)$$$
Valid roots (vertex numbers)$$$\{1,2,3\}$$$$$$\{1\}$$$$$$\{3\}$$$$$$\{3\}$$$$$$\{1\}$$$$$$\{1,2,3\}$$$
The sum of the search qualities is $$$3+1+1+1+1+3=10$$$.