There is a tree with $n$ nodes. Let $w(u, v)$ denote the simple path$^\dagger$ between two nodes $u$ and $v$ in the tree. A subset $S$ of the set of all simple paths in the tree$^\star$ is called good if and only if:

• Every edge $(u, v)$ in the tree is covered by exactly one path in $S$$^\ddagger$.

For a good set $S$, let $f(S)$ be the maximum number of times any node $i$ appears as an endpoint of a path in $S$ for all $1 \leq i \leq n$. Formally, $f(S) = \max\limits_{i=1}^n \left(\sum\limits_{w(u, v) \in S} [u = i \lor v = i]\right)$.

You need to count how many good sets $S$ satisfy $f(S) = \min\limits_{S\text{ is good}}(f(S))$ (i.e., the minimum value of $f(T)$ among all good sets $T$), modulo $998244353$.

$\dagger$: A path is a simple path if and only if it does not visit any node more than once. There is exactly one simple path between any two nodes $u, v$ in a tree.

$\star$: The set of all simple paths in the tree can be viewed as the set of paths $w(u, v)$ for every pair of nodes $(u, v)$ where $1 \leq u \leq v \leq n$.

$\ddagger$: An edge $(u, v)$ is covered by a simple path $s \leadsto t$ if and only if both nodes $u$ and $v$ lie on the simple path $s \leadsto t$.

Input

This problem contains multiple test cases.

The first line contains an integer $t$ ($1 \leq t \leq 2\cdot 10^4$), representing the number of test cases. For each test case:

• The first line contains an integer $n$ ($2 \leq n \leq 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$), representing an edge between node $u$ and node $v$.

It is guaranteed that the given edges form a tree, and 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 good sets $S$ such that $f(S)$ attains its minimum possible value, modulo $998244353$.

Examples

Input 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

Output 1

1
9
45

Note

For the first test case, there are two good sets $S$:

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

Since $f(\{w(1, 3)\}) = 1$ (nodes $1$ and $3$ each appear $1$ time), and $f(\{w(1, 2), w(2, 3)\}) = 2$ (node $2$ appears $2$ times), only $\{w(1, 3)\}$ is a good set that attains the minimum, so the answer is $1$.