L. A Game On Tree
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

There is a tree (a connected undirected graph with $$$n$$$ nodes and $$$n-1$$$ edges) consisting of $$$n$$$ nodes, with nodes numbered from $$$1$$$ to $$$n$$$. Clearly, there is a unique simple path between any two nodes in the tree.

Xiaohong and Xiaolan are playing a game on this tree. In each game, both players independently and uniformly select a random simple path from all $$$\frac{n(n-1)}{2}$$$ simple paths (regardless of direction) that exist in the tree. Note that they may choose the same path. Let $$$X$$$ denote the number of edges that are common to both selected paths, and the score of the game is $$$X^2$$$.

Your task is to find the expected value of the score $$$E(X^2)$$$ when Xiaohong and Xiaolan play the game once, and output the result modulo $$$998244353$$$ (see the output format for details).

Input

The first line contains a positive integer $$$T$$$ ($$$1\le T \le 10^4$$$), representing the number of test cases.

For each test case, the first line contains a positive integer $$$n$$$ ($$$2\le n \le 10^5$$$), representing the number of nodes in the tree.

The next $$$n-1$$$ lines each contain two positive integers $$$u, v$$$ ($$$1\le u,v \le n$$$), indicating that there is an edge between nodes $$$u$$$ and $$$v$$$. The input is guaranteed to be a tree.

The sum of all $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

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

Formally, let $$$M=998244353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac p q$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not\equiv 0\pmod M$$$. Output the integer equal to $$$p\cdot q^{-1}\pmod M$$$, where $$$q^{-1}$$$ denotes the modular multiplicative inverse of $$$q$$$ modulo $$$M$$$. In other words, output such an integer $$$x$$$ that $$$0\le x \lt M$$$ and $$$x\cdot q\equiv p\pmod M$$$. It can be proved that there is exactly one $$$x$$$ which meets the condition.

Example
Input
2
3
1 2
2 3
5
1 2
1 5
3 2
4 2
Output
443664158
918384806
Note

For the first test case in the example, the answer without taking the modulo is $$$\frac{10}{9}$$$.

Among the $$$9$$$ possible cases:

  • In $$$2$$$ cases, the number of common edges between the two paths is $$$0$$$;
  • In $$$6$$$ cases, the number of common edges between the two paths is $$$1$$$;
  • In $$$1$$$ case, the number of common edges between the two paths is $$$2$$$.

Therefore, the answer is $$$E(X^2) = \frac{2 \cdot 0^2 + 6 \cdot 1^2 + 1 \cdot 2^2}{9} = \frac{10}{9}$$$.