G. Fairy Lights
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree on $$$n$$$ vertices. Every vertex carries a light, and initially all $$$n$$$ lights are on.

You then repeatedly perform the following operation:

  • choose an edge whose two endpoints are both currently on, and turn off the lights at both of them.

Once a light is turned off it never turns back on. You keep performing the operation until no edge has both of its endpoints on, that is, until the operation can no longer be performed.

Depending on the order in which you choose the edges, you may end up with different sets of vertices whose lights are still on. Count the number of distinct such sets of vertices that are reachable when you stop. Since this number can be large, output it modulo $$$998244353$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of vertices of the tree.

Each of the next $$$n - 1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$; $$$u \ne v$$$) — an edge of the tree. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, output a single integer — the number of distinct reachable sets of on lights when you stop, modulo $$$998244353$$$.

Example
Input
4
3
1 2
2 3
4
1 2
1 3
1 4
4
1 2
2 3
3 4
5
1 2
1 3
3 4
3 5
Output
2
3
2
3
Note

In the first test case, the tree is the path $$$1 - 2 - 3$$$. There are two ways the process can go:

  • Turn off the lights at the endpoints of edge $$$1 - 2$$$. Now only vertex $$$3$$$ is on, and no edge has both endpoints on, so you stop. The set of on lights is $$$\{3\}$$$.
  • Turn off the lights at the endpoints of edge $$$2 - 3$$$. Now only vertex $$$1$$$ is on, and you stop. The set of on lights is $$$\{1\}$$$.

These give two distinct final sets, $$$\{3\}$$$ and $$$\{1\}$$$, so the answer is $$$2$$$.

In the second test case, the tree is a star with center $$$1$$$. Whichever edge $$$1 - i$$$ you choose first, vertices $$$1$$$ and $$$i$$$ turn off and the two remaining leaves stay on with no edge left to use. The reachable final sets are $$$\{3, 4\}$$$, $$$\{2, 4\}$$$, and $$$\{2, 3\}$$$, so the answer is $$$3$$$.

In the third test case, the tree is the path $$$1 - 2 - 3 - 4$$$. If you first use edge $$$2 - 3$$$, you stop with vertices $$$1$$$ and $$$4$$$ on. Otherwise you first use one of the end edges, after which the opposite end edge still has both endpoints on and must be used, leaving every light off. The reachable final sets are $$$\{1, 4\}$$$ and $$$\{\,\}$$$, so the answer is $$$2$$$.