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.
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$$$.
For each test case, output one integer representing the answer modulo $$$998244353$$$.
351 21 33 43 561 21 31 42 52 661 22 32 43 54 6
11 18 16
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$$$.
