There are a total of 426 inhabitants in Crasna, according to the 2021 census. This brings great sadness to Little IR12660, who wants this village to flourish. So he planted a tree there.
The tree Little IR12660 planted is a very special one that will grow to have $$$N$$$ nodes. Little IR12660 knows that each node will have an initial label and a friendship label. All initial labels are pairwise distinct values from $$$1$$$ to $$$N$$$, and all friendship labels are pairwise distinct values from $$$0$$$ to $$$N - 1$$$. Little IR12660 also knows how the nodes will be connected among them according to the initial labels. However, he doesn't know anything about the friendship labels, as they develop according to many unpredictable environmental factors.
Little IR12660 doesn't have time to watch his tree actually grow. So he wonders in how many ways can the friendship labels be associated to the nodes such that the sum of the MEX$$$^{\ddagger}$$$ of all the paths in the tree is minimized.
$$$^{\ddagger}:$$$ The MEX of a set is the smallest natural number that does not belong to the set.
The first line contains a single integer $$$T$$$ ($$$1 \le T \le 30\,000$$$), the number of test cases. For each test case:
The first line contains one integer $$$N$$$ ($$$1 \le N \le 200\,000$$$), the number of nodes of the tree.
Then, $$$N - 1$$$ lines follow, each with two integers, $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le N, x_i \neq y_i$$$), denoting there is an edge between the node with initial label $$$x_i$$$ and the one with initial label $$$y_i$$$.
It is guaranteed that the sum of $$$N$$$ over all testcases is at most $$$200\,000$$$.
For each testcase, print the answer modulo $$$998\,244\,353$$$.
396 84 82 95 71 94 77 37 182 73 66 84 36 12 46 531 23 1
34560 5040 2
For the third testcase, the two ways the friendship labels can be associated to the nodes with initial labels $$$[1, 2, 3]$$$ are $$$[2, 0, 1]$$$ and $$$[2, 1, 0]$$$.
