J. Equal Node Sum
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You're given a rooted tree with $$$n$$$ vertices. The root node is $$$1$$$. You can set the weight of each edge to either $$$0$$$ or $$$1$$$. We call the sum value of node $$$i$$$ the sum of the weights of all edges incident to it.

Count the number of different assignments of edge weights that satisfy the following condition.

  • For each non-leaf node$$$^\dagger$$$, its sum value is equal to the sum value of every other non-leaf node.

Since the answer may be large, output the answer modulo $$$998\,244\,353$$$.

$$$^\dagger$$$ A node is called a non-leaf node if and only if it is the root node $$$1$$$ or there are at least $$$2$$$ edges incident to it.

Input

The input consists of multiple test cases. The first line of the input contains an integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$), the number of test cases.

For each test case:

  • The first line contains an integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$), the number of nodes in the tree.
  • The next $$$n-1$$$ lines each contain two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$), indicating an edge between nodes $$$u$$$ and $$$v$$$. It is guaranteed that the given input forms a tree.

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

Output

For each test case, output a single integer representing the number of different trees satisfying the given condition, modulo $$$998\,244\,353$$$.

Example
Input
5
3
1 2
1 3
3
1 2
2 3
4
1 4
2 4
3 1
6
1 4
2 3
3 6
4 3
5 2
8
1 2
2 4
3 4
4 8
5 1
6 4
7 3
Output
4
2
4
3
6
Note

In the first test case, there is only one non-leaf node: node $$$1$$$. You can set edge weights arbitrarily; thus, there are $$$4$$$ different assignments of edge weights.

In the second test case, there are two non-leaf nodes: nodes $$$1$$$ and $$$2$$$. There are $$$2$$$ valid assignments as shown below.

The two valid assignments.