K. The Only Heart
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Kikyou has carefully cultivated a tree. Now that the tree has grown lush with branches and leaves, Kikyou decides to prune it.

The tree currently has $$$n$$$ vertices. Kikyou plans to remove some vertices and their adjacent edges such that the remaining part is still connected. It is easy to see that the remaining part is still a tree.

As a heavy cat, Kikyou wants the remaining tree to be wholehearted, meaning it has only one heart. Here, the heart of a tree is defined as a vertex such that when it is removed, the maximum size among the remaining connected components is minimized. If multiple vertices satisfy this condition, they are all considered hearts.

Kikyou wants to know how many such remaining non-empty trees there are where the heart is unique. Output the answer modulo $$$998244353$$$. Two remaining trees are considered different if and only if their vertex sets are different.

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
3 4
3 5
6
1 2
1 3
1 4
2 5
2 6
6
1 2
2 3
2 4
3 5
4 6
Output
11
18
16
Note

For the first test case, a single remaining vertex must be the unique heart. Two remaining vertices must form two hearts. Other valid subsets with unique heart include: $$$\{1,2,3\}$$$, $$$\{1,3,4\}$$$, $$$\{1,3,5\}$$$, $$$\{3,4,5\}$$$, $$$\{1,3,4,5\}$$$, and $$$\{1,2,3,4,5\}$$$. The total number of valid subsets is $$$11$$$.