請注意本題入面關於子樹同直徑嘅非標準定義。

以下係一啲定義：

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