题目描述

有一棵 $n$ 个节点的树。令 $w(u, v)$ 表示树上 $u, v$ 两点之间的简单路径$^\dagger$。称一个树上所有简单路径组成的集合$^\star$ 的子集 $S$ 是好的，当且仅当：

• 树上每条边 $(u, v)$ 都被 恰好一条 $S$ 中的路径覆盖$^\ddagger$。

对于一个好的集合 $S$，设 $f(S)$ 表示对所有 $1 \leq i \leq n$，结点 $i$ 在 $S$ 中作为某条路径端点的出现次数的最大值。形式化地，$f(S) = \max\limits_{i=1}^n \left(\sum\limits_{w(u, v) \in S} [u = i \lor v = i]\right)$。

你需要统计有多少个好的集合 $S$ 满足 $f(S)$ 取到 $\min\limits_{S\text{ is good}}(f(S))$（也就是所有好的集合 $T$ 中，$f(T)$ 的最小值），答案对 $998244353$ 取模。

$\dagger$：一条路径是简单路径，当且仅当其不重复经过任何结点。树上任意两个结点 $u, v$ 之间有且仅有一条简单路径。

$^\star$：树上所有简单路径组成的集合，可以看做对每个 $1 \leq u \leq v \leq n$ 的节点对 $(u, v)$，$w(u, v)$ 组成的集合。

$\ddagger$：称边 $(u, v)$ 被简单路径 $s \leadsto t$ 覆盖，当且仅当点 $u, v$ 均在 $s \leadsto t$ 的简单路径上。

输入格式

本题单个测试点内有多组测试数据。

第一行，一个整数 $t$（$1 \leq t \leq 2\cdot 10^4$），描述数据组数。对于每组数据：

• 第一行，一个整数 $n$（$2 \leq n \leq 10^5$），表示树中的结点数。
• 接下来 $n - 1$ 行，每行两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$），表示一条在结点 $u$ 和结点 $v$ 之间的连边。

保证给出的所有边构成一棵树；保证对单个测试点，所有 $n$ 的和不超过 $2\cdot 10^5$。

输出格式

对于每组数据，输出一行一个整数，表示好的集合 $S$ 中，满足 $f(S)$ 取到其能够取到的最小值的集合数量，答案对 $998244353$ 取模。

样例

样例输入 1

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

样例输出 1

1
9
45

样例解释

对于第一组数据，好的集合 $S$ 共有两个：

• $\{w(1, 2), w(2, 3)\}$；
• $\{w(1, 3)\}$。

因为 $f(\{w(1, 3)\}) = 1$（结点 $1, 3$ 都出现了 $1$ 次），而 $f(\{w(1, 2), w(2, 3)\}) = 2$（结点 $2$ 出现了 $2$ 次），因此只有 $\{w(1, 3)\}$ 是好的，答案为 $1$。