Problem Statement

You are given a tree $G$ with $N$ vertices and $N-1$ edges. The vertices are numbered $1$ to $N$, and the edges are numbered $1$ to $N-1$. Edge $i$ connects vertices $u_i$ and $v_i$.

A tree $H$ is called special if it is possible to delete all edges of $H$ by performing the following operation zero or more times.

• Choose an edge connecting two vertices whose current degrees are equal, and delete it.

Find the number of special subtrees of $G$, modulo $998244353$.

Solve $T$ test cases for each input.

What is a subtree? A subtree of a tree $G$ is a connected subgraph of $G$.

Constraints

• $1 \leq T \leq 10^5$
• $2 \leq N \leq 3 \times 10^5$
• The sum of $N$ over all test cases is at most $3 \times 10^5$.
• $1 \leq u_i \lt v_i \leq N$
• The given graph $G$ is a tree.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case $\mathrm{case}_t$ is given in the following format:

N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}

Output

Print $T$ lines in total. The $t$-th line should contain the answer for the $t$-th test case.