Namesolo 迷上了游戏《Stick Fight》。但在玩游戏时，他想知道如何找出游戏中的火柴人数量。

在本题中，我们定义如上图所示的火柴人。它由一条长度为 1 的链作为头部，两条长度为 2 的链作为手臂，一条长度为 1 的链作为身体，以及两条长度为 1 的链作为腿部组成。例如，图中红色的部分可以被视为一个火柴人，其中链 $(2, 3)$ 为头部，链 $(3, 4, 6)$ 和 $(3, 9, 10)$ 为手臂，链 $(3, 5)$ 为身体，链 $(5, 7)$ 和 $(5, 8)$ 为腿部。

该游戏可以看作一棵树，Namesolo 想知道其中有多少个火柴人。请注意，如果两个火柴人所构成的边集中至少有一条边不同，则这两个火柴人被视为不同的。

由于答案可能非常大，Namesolo 想知道答案对 $998244353$ 取模的结果。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 15$)，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 5 \times 10^5$)，表示树的顶点数。接下来的 $n-1$ 行，每行包含两个整数 $a, b$ ($1 \le a, b \le n$)，表示树中存在一条连接 $a$ 和 $b$ 的边。

保证所有测试用例中 $n$ 的总和不超过 $3 \times 10^6$。

输出格式

对于每个测试用例，输出一个整数，表示答案对 $998244353$ 取模的结果。

样例

样例输入 1

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

样例输出 1

1