C. Least Compatible Ancestor
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given a rooted tree with $$$n$$$ nodes numbered from $$$1$$$ to $$$n$$$ and the root of the tree is node $$$1$$$. Find the number of ways, modulo $$$998244353$$$, to assign a value $$$a_u$$$ to each node $$$u$$$ such that $$$1 \le a_u \le n$$$ and $$$a_{\text{lca}(i, j)} \neq \text{lca}(a_i, a_j)$$$ is satisfied over all pairs $$$1 \le i \lt j \le n$$$, where $$$\text{lca}(x, y)$$$ denotes the lowest common ancestor of nodes $$$x$$$ and $$$y$$$ in the tree.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 5$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 20$$$) — the number of nodes in the tree.

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$) indicating there is an edge between nodes $$$u$$$ and $$$v$$$. It is guaranteed that the given edges form a tree.

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

Output

For each test case, output a single integer — the number of ways to assign values to all nodes satisfying the given condition, modulo $$$998244353$$$.

Example
Input
2
2
1 2
3
1 3
2 1
Output
1
8
Note

In the first test case, there is only one valid way to assign values to the nodes: $$$a_1 = 2$$$ and $$$a_2 = 1$$$. In this case, the condition is satisfied because for the pair $$$(1, 2)$$$, $$$a_{\text{lca}(1, 2)} = a_1 = 2$$$ and $$$\text{lca}(a_1, a_2) = \text{lca}(2, 1) = 1$$$, so they are not equal.