题目描述

给定一棵包含 $n$ 个节点的树（包含 $n$ 个节点和 $n-1$ 条边的连通无向图），节点编号为 $1$ 到 $n$。显然，树上任意两个节点之间有且仅有一条简单路径。

小红和小蓝在这棵树上玩游戏。在一次游戏中，两人会从树上至少包含了一条边的所有 $\frac{n(n-1)}{2}$ 条简单路径（不考虑路径的方向）中，$\textbf{独立且等概率地}$ 随机选择一条简单路径（注意两人可能选择同一条简单路径）。记选择的两条路径包含的公共边数量是 $X$，则本次游戏的得分是 $X^2$。

求小红和小蓝进行一次游戏的得分的数学期望 $E(X^2)$，输出在 $998244353$ 模意义下的结果（详情见输出格式）。

输入格式

第一行一个正整数 $T$ ($1\le T \le 10^4$)，表示测试数据组数。

对于每组测试数据，第一行包含一个正整数 $n$ ($2\le n \le 10^5$)，表示树的节点数量。

接下来 $n-1$ 行，每行包含两个正整数 $u, v$ ($1\le u,v \le n$)，表示节点 $u$ 和节点 $v$ 之间有一条边。保证输入是一棵树。

保证所有测试数据的 $n$ 的和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行一个整数，表示答案在 $998244353$ 模意义下的结果。

令 $M=998244353$。可以证明，答案能够表示为最简分数 $\frac p q$，其中 $p$ 和 $q$ 是正整数且 $q \not\equiv 0\pmod M$。则你需要输出 $p\cdot q^{-1}\pmod M$，$q^{-1}$ 表示 $q$ 在模 $M$ 意义下的乘法逆元。换句话说，输出满足 $0\le x < M$ 且 $x\cdot q\equiv p\pmod M$ 的整数 $x$。可以证明，符合条件的 $x$ 是唯一的。

2
3
1 2
2 3
5
1 2
1 5
3 2
4 2

443664158
918384806

提示

对于样例的第一组数据，未取模的答案是 $\frac{10}{9}$。

在 $9$ 种可能的情况中：

• $2$ 种情况两条路径的公共边数量为 $0$；
• $6$ 种情况两条路径的公共边数量为 $1$；
• $1$ 种情况两条路径的公共边数量为 $2$。

故答案 $E(X^2) = \frac{2 \cdot 0^2 + 6 \cdot 1^2 + 1 \cdot 2^2}{9} = \frac{10}{9}$。