题目描述

Tsumugi 喜欢画画。

这一天，Tsumugi 拿到了不知道是谁忘下的泡泡纸，于是她剪下来 $n$ 个泡泡贴在了白板上，然后画了一些边，构成了一棵树。Tsumugi 将每个泡泡进行了编号，并指定了 $1$ 号泡泡为根，形成一棵有根树。

Chinatsu 看到之后很想捏爆一些泡泡，于是选择了飞扑过去，然后捏泡泡玩。

在远处偷偷拍照的 Mia 在按下快门之余还在思考，有多少种方案，满足 Chinatsu 在捏爆泡泡后，满足每个子树，被捏爆的泡泡和没被捏爆的泡泡的数量相差至多 $1$？

由于可能的方案数很多，即使是作为优等生的 Mia 也算不出来，于是她请你编写一个程序，求出方案数对 $998244353$ 取模的值。

转眼之间 Tsumugi 贴出来了 $T$ 棵树，你需要对每棵树都求出对应的答案。

输入格式

第一行一个正整数 $T$，代表树的数量，

接下来每棵树，第一行一个正整数 $n$，表示这棵树含有的泡泡数量。然后 $n-1$ 行，每行共两个整数 $u,v$，表示泡泡 $u$ 和泡泡 $v$ 相连。保证形成一棵树。

输出格式

共 $T$ 行，每行一个整数，表示每棵树的方案数对 $998244353$ 取模的值。

2
3
1 2
2 3
3
1 2
1 3

4
6

数据范围

• 对于 $30\%$ 的数据，$1 \le T \le 15$，$1 \le n, \sum n \le 15$。
• 对于另外 $30\%$ 的数据，每个根节点以外的泡泡的度数均小于等于 $2$（即，最多只有两个泡泡与其有边相连）。
• 对于 $100\%$ 的数据，$1 \le T \le 2 \cdot 10^5$，$1 \le n, \sum n \le 2 \cdot 10^5$，保证输入的图是一棵树。