H. Tree Shuffling
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Froggy has an unrooted tree $$$T$$$ with $$$n$$$ vertices, where each vertex has an initial weight. Initially, the weight of vertex $$$i$$$ is $$$i$$$.

Froggy can perform at most 1 operation sequentially as follows:

  • Select several distinct vertices $$$x_1, x_2, \cdots, x_k$$$, such that for $$$i = 1, 2, \cdots, k-1$$$, there exists an edge in tree $$$T$$$ connecting vertex $$$x_i$$$ and vertex $$$x_{i+1}$$$.
  • From the set $$${x_1, x_2, \cdots, x_k}$$$, choose an even number of vertices $$$u_1, u_2, \cdots, u_{2l}$$$ (vertices can be chosen repeatedly). For $$$i = 1, 2, \cdots, l$$$, sequentially swap the weights of vertex $$$u_{2i-1}$$$ and vertex $$$u_{2i}$$$.

Let $$$a_i$$$ denote the weight of vertex $$$i$$$ after all operations. How many distinct sequences $$$a_1, a_2, \cdots, a_n$$$ can Froggy obtain? Output the answer modulo $$$998244353$$$.

Input

The first line contains a positive integer $$$T$$$ $$$(1 \leq T \leq 10^3)$$$, indicating the number of test cases.

For each test case, the first line contains an integer $$$n$$$ $$$(1 \leq n \leq 3000)$$$, representing the number of vertices in the tree.

The next $$$n-1$$$ lines each contain two positive integers $$$x, y$$$ $$$(1 \leq x, y \leq n, x \neq y)$$$, representing the two endpoints of an edge in tree $$$T$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases in a single test point does not exceed $$$1.5 \times 10^4$$$.

Output

For each test case, output one integer representing the answer modulo $$$998244353$$$.

Example
Input
3
5
1 2
1 3
1 4
1 5
6
1 2
1 3
1 4
2 5
2 6
6
1 2
2 3
2 4
3 5
4 6
Output
23
80
155