請注意本題中關於子樹與直徑的非標準定義。

以下是一些定義：

• 一棵樹 $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。