Note the unusual definition of subtree and diameter in this problem.

Here are some definitions:

• The size of a tree $T$ is the number of vertices in it, that is, $|V(T)|$.
• The degree of a vertex $i$ in tree $T$ is the number of edges connected to it, denoted by $\operatorname{deg}_i$.
• A tree $T'$ is a subtree of tree $T$ if and only if:
  • For all vertices $v \in V(T')$, $v \in V(T)$.
  • For all edges $e \in E(T')$, $e \in E(T)$.
• Let $S_T$ be the set of subtrees of $T$.
• The diameter of a tree $T$ is the size of the largest subtree of $T$ such that $\max(\operatorname{deg}_i) \le 2$ in the subtree.
• Let $R_x$ be the set of the largest trees such that:
  • $\max(\operatorname{deg}_i) \le 3$.
  • The diameter of the tree is $2x$.
• For a tree $T$, let $f(T)$ be the largest $k$ such that $S_T \cap R_k \ne \emptyset$. If there's no such $k$, $f(T) = 0$.

You are given a tree $T$ with $n$ nodes. Count sum of $f(T')$ for all subtrees $T'$ of $T$ modulo $998244353$. Two subtrees are different if and only if they have different vertex set or edge set.

Input

Each test contains multiple test cases. The first line contains one integer $t$ ($1 \le t \le 5 \times 10^4$), indicating the number of test cases. The description of the test cases follows.

The first line contains one integer $n$ ($1 \le n \le 10^5$, $\sum n \le 10^6$), indicating the number of vertices in the tree $T$.

Each of the following $n - 1$ lines contains two integers $u, v$ ($1 \le u \ne v \le n$), indicating an edge on the tree $T$.

Output

For each test case, print one integer, indicating the sum of $f(T')$, modulo $998244353$.

Example

Input

2
5
1 2
1 3
2 4
2 5
8
1 2
8 7
1 3
8 6
1 4
8 5
1 8

Output

12
94

Note

For the first test case, there are 17 different subtrees. 5 of the subtrees contain only one vertex and thus $f(T') = 0$. All the other subtrees satisfy $f(T') = 1$. Thus, the answer is 12.