Rikka with Line Graph

Problem Description

Line Graph $L(G)$ can be considered as an operator on an undirected graph $G$ just like Complementary Graph and Dual Graph. Rikka generalizes Line Graph to edge-weighted undirected graphs. For a graph $G=\langle V,E\rangle$, $L(G)$ is still an edge-weighted undirected graph which is constructed in the following way:

1. $L(G)$ has $|E|$ vertices and the $i$th vertex corresponds to the $i$th edge in $G$.

2. There is an edge between $i,j$ in $L(G)$ if and only if edge $i$ and $j$ have at least one common vertices in $G$. And the edge weight is equal to the sum of the weights of edge $i$ and $j$ in $G$. For example, in the following picture, the right graph is the line graph of the left one. Vertex $1,2,3,4$ in $L(G)$ correspond to edge $(1,2),(1,4),(1,3),(3,4)$ in $G$. And if all edges in the left graph have weight $1$, the edges in the right graph will have weight $2$.

   Now, Rikka has an edge-weighted tree $T$ with $n$ vertices. And she constructs a graph $G=L(L(T))$. It is clear that $G$ is connected. Let $d(i,j)$ be the length of the shortest path between vertex $i,j$ in $G$(the length of each edge is equal to the weight), $m$ be the number of vertices in $G$, Rikka wants you to calculate $\sum_{i=1}^m \sum_{j=i+1}^m d(i,j)$.

Input

The first line contains a single number $t(1 \leq t \leq 100)$, the number of the testcases. For each testcase, the first line contains one single integer $n(1 \leq n \leq 10^5)$. Then $n-1$ lines follow, each line contains three integers $u_i,v_i,w_i(1 \leq u_i,v_i \leq 10^5, 1 \leq w_i \leq 10^9)$, describe an edge with weight $w_i$ between $u_i$ and $v_i$. The input guarantees that $G$ has at least one vertices and there are at most $5$ testcases with $n>10^3$.

Output

For each testcase, output a single line with a single number, the answer modulo $998244353$.

Sample Input

3

4

1 2 1

1 3 2

1 4 3

5

1 2 1

2 3 10

2 5 7

3 4 2

10

1 2 1

1 3 1

2 4 1

2 5 1

2 6 1

3 7 1

7 8 1

5 9 1

6 10 1

Sample Output

24

166

420

Source

2018 Multi-University Training Contest 9