题目描述

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

以下是一些定义：

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

给定一棵有 $n$ 个节点的树 $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 \neq v \le n$)，表示树 $T$ 上的一条边。

输出格式

对于每组测试数据，打印一个整数，表示 $f(T')$ 的总和，模 $998244353$。

样例

样例输入 1

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

样例输出 1

12
94

说明

对于第一个测试用例，有 17 棵不同的子树。其中 5 棵子树只包含一个顶点，因此 $f(T') = 0$。所有其他子树都满足 $f(T') = 1$。因此，答案是 12。