对于一个长度为 $n$ 的整数序列 $a_1, \dots, a_n$，其逆序对数 $inv(a)$ 定义为满足 $1 \le i < j \le n$ 且 $a_i > a_j$ 的整数对 $(i, j)$ 的数量。

对于一棵给定的 $n$ 个节点的有根树（顶点编号为 $1$ 到 $n$），其上的 DFS 过程如下： - 在过程中，我们维护一个当前顶点 $u$ 和一个已访问顶点集合 $M$。 - 设树的根为 $x$。初始时，$u = x$ 且 $M = \{x\}$。 - 重复以下过程，直到 $M$ 包含所有顶点： - 如果 $u$ 至少有一个不在 $M$ 中的子节点，则等概率地从中随机选择一个顶点（记为 $v$）。将 $u$ 更新为 $v$，并将 $v$ 加入 $M$。 - 否则，将 $u$ 更新为 $u$ 的父节点。

对于每个 $u = 1, \dots, n$，我们记录 $u$ 被加入 $M$ 时 $M$ 中顶点的数量（包含 $u$ 本身）。记该数量为 $d_u$。我们将 $(d_1, d_2, \dots, d_n)$ 称为一个 DFS 序列。由于 DFS 过程是非确定性的，产生的 DFS 序列也可能不同。假设 DFS 过程中的每一次决策都是独立的。

给定一棵 $n$ 个顶点的无根树，顶点编号为 $1$ 到 $n$。对于每个 $i = 1, \dots, n$，计算以 $i$ 为根并开始 DFS 过程时，DFS 序列的期望逆序对数。为了避免精度误差，请输出答案对 $998244353$ 取模的结果。

共有 $T$ 组独立的测试数据。请解决每一组数据。

关于如何计算非整数模 $998244353$：可以证明该问题的答案总能写成一个分数 $P/Q$，其中 $P, Q$ 为整数且 $Q \not\equiv 0 \pmod{998244353}$。存在唯一的整数 $R \in [0, 998244353)$ 满足 $QR \equiv P \pmod{998244353}$。请输出该 $R$ 作为答案。

输入格式

输入的第一行包含一个整数 $T(1 \le T \le 10)$，表示测试用例的数量。接下来是 $T$ 组测试用例。 每组测试用例的第一行包含一个整数 $n(1 \le n \le 10^5)$，表示树的顶点数。接下来的 $n - 1$ 行，每行包含两个整数 $u, v(1 \le u, v \le n)$，表示树上的一条边。保证输入的边构成一棵树。

输出格式

对于每组测试用例，输出 $n$ 行。第 $i$ 行应包含以顶点 $i$ 为根时，DFS 序列的期望逆序对数。

样例

输入 1

1
3
1 2
1 3

输出 1

499122177
1
2