#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/3/problems/E

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████

Different Distances - Repovive Premier Round 2 | Repovive | Repovive

3E. Different Distances

2500 pts2s256 MB

You are given a tree with $n$ vertices numbered from $1$ to $n$ .

A subset of vertices $S$ is called good if for every two distinct vertices $1 \le v,u \le n$ , there exists a vertex $x \in S$ such that $dist(v,x) \ne dist(u,x)$ .

Compute the number of good subsets $S$ , modulo $998244353$ .

Constraints

$1 \le t \le 10^4$
$3 \le n \le 2 \times 10^5$
The given graph is a tree, it has exactly $n-1$ edges
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \times 10^5$

Input

t \\[0.5em] \left. \begin{array}{l} n \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_{n-1} \quad v_{n-1} \end{array} \right\} \times t

Output

\left. \begin{array}{l} ans \end{array} \right\} \times t

Samples

Input

Case 1

Case 2

Case 3

Case 4

Explanation

Case 1

This tree is a simple path $1-2-3-4-5$ . For example, $S=\{2,3\}$ is good, because for any two distinct vertices $u \ne v$ , at least one of $x=2$ or $x=3$ has different distances to them, so $dist(u,x) \ne dist(v,x)$ . On the other hand, $S=\{3\}$ is not good, because vertices $2$ and $4$ have the same distance to $3$ , so $dist(2,3)=dist(4,3)=1$ , and there is no other vertex in $S$ to distinguish them.

Case 2

This tree has a branching at vertex $2$ (edges $1-2$ , $2-3$ , $2-4$ ). For example, $S=\{1,3\}$ is good, since every pair of vertices can be distinguished using either $x=1$ or $x=3$ . However, $S=\{2\}$ is not good, because vertices $1$ and $3$ have the same distance to $2$ , so $dist(1,2)=dist(3,2)=1$ .

Output

Case 1

Case 2

Case 3

Case 4

You are given a tree with $n$ vertices numbered from $1$ to $n$ .

A subset of vertices $S$ is called good if for every two distinct vertices $1 \le v,u \le n$ , there exists a vertex $x \in S$ such that $dist(v,x) \ne dist(u,x)$ .

Compute the number of good subsets $S$ , modulo $998244353$ .

Constraints

$1 \le t \le 10^4$
$3 \le n \le 2 \times 10^5$
The given graph is a tree, it has exactly $n-1$ edges
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \times 10^5$

t \\[0.5em] \left. \begin{array}{l} n \\ u_1 \quad v_1 \\ u_2 \quad v_2 \\ \vdots \\ u_{n-1} \quad v_{n-1} \end{array} \right\} \times t

\left. \begin{array}{l} ans \end{array} \right\} \times t

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

3E. Different Distances

Input

Output

Samples

3E. Different Distances

Constraints

Input

Output

Samples

Constraints