For an integer sequence $a_1,...,a_n$ of length $n$, its inversion number $\mathrm{inv}(a)$ is defined as the number of integer pairs $(i,j)$ such that $1\leq i < j\leq n$ and $a_i > a_j$.
For a given rooted tree of $n$ nodes (with vertices numbered from $1$ to $n$), a **DFS procedure** on the tree is as following.
- During the process, we maintain a **current vertex**, namely $u$, and a **set of visited vertices**, namely $M$.
- Let the root of the tree be $x$. Initially, $u=x$ and $M=\{x\}$.
- Repeat the following process until $M$ contains all vertices:
- - If there is at least one child vertex of $u$ that is not in $M$, randomly choose one among those vertices equiprobably (namely $v$). Set $u$ to $v$ and add $v$ to $M$.
- Otherwise, set $u$ to the father of $u$.
For each $u=1,...,n$, we record the number of vertices in $M$ when $u$ is added to $M$ (including $u$). Let this number be $d_u$. We call $(d_1,d_2,...,d_n)$ a **DFS order**. As **DFS procedure** is non-deterministic, the resulting **DFS order** may vary as well. Assume that each decision in the **DFS procedure** is independent.
You are given an unrooted tree of $n$ vertices, with vertices numbered from $1$ to $n$. For each $i=1,...,n$, compute the expected inversion number of the **DFS order** when rooting the tree at $i$ and start a **DFS procedure**. To avoid precision errors, print the answer modulo $998244353$.
You are given $T$ independent test cases. Solve each of them.
**How to compute non-integers modulo $998244353$:** It can be proved that the answer to this problem can always be written as a fraction $\dfrac{P}{Q}$ with $P,Q$ being integers and $Q\not\equiv 0\pmod{998244353}$. There is exactly one integer $R\in [0,998244353)$ that satisfies $QR\equiv P\pmod{998244353}$. Print this $R$ as the answer.