请注意本题中关于子树和直径的非标准定义。

以下是一些定义：

• 一棵树 $T$ 的大小是指其顶点数，即 $|V(T)|$。
• 树 $T$ 中顶点 $i$ 的度数是指与其相连的边数，记作 $\operatorname{deg}_i$。
• 一棵树 $T'$ 是树 $T$ 的子树，当且仅当：
  • 对于所有顶点 $v \in V(T')$，有 $v \in V(T)$。
  • 对于所有边 $e \in E(T')$，有 $e \in E(T)$。
• 令 $S_T$ 为 $T$ 的所有子树的集合。
• 一棵树 $T$ 的直径是指 $T$ 的满足子树内 $\max(\operatorname{deg}_i) \le 2$ 的最大子树的大小。
• 令 $R_x$ 为满足以下条件的最大树的集合：
  • $\max(\operatorname{deg}_i) \le 3$。
  • 该树的直径为 $2x$。
• 对于一棵树 $T$，令 $f(T)$ 为满足 $S_T \cap R_k \ne \emptyset$ 的最大整数 $k$。如果不存在这样的 $k$，则 $f(T) = 0$。

给定一棵有 $n$ 个节点的树 $T$。求 $T$ 的所有子树 $T'$ 的 $f(T')$ 之和对 $998244353$ 取模的结果。两棵子树不同当且仅当它们的点集或边集不同。

输入格式

每个测试点包含多组测试数据。第一行包含一个整数 $t$（$1 \le t \le 5 \times 10^4$），表示测试数据组数。接下来是各组测试数据的描述。

每组测试数据的第一行包含一个整数 $n$（$1 \le n \le 10^5$，$\sum n \le 10^6$），表示树 $T$ 的顶点数。

接下来的 $n - 1$ 行，每行包含两个整数 $u, v$（$1 \le u \ne v \le n$），表示树 $T$ 上的一条边。

输出格式

对于每组测试数据，输出一个整数，表示 $f(T')$ 之和对 $998244353$ 取模的结果。

样例

输入

2
5
1 2
1 3
2 4
2 5
8
1 2
8 7
1 3
8 6
1 4
8 5
1 8

输出

12
94

说明

对于第一组测试数据，共有 17 棵不同的子树。其中 5 棵子树仅包含一个顶点，因此 $f(T') = 0$。其余所有子树都满足 $f(T') = 1$。因此答案为 12。