WO MEI K

Problem Description

There is a weighted tree with $n$ vertices and $n-1$ edges. each edge has a value. Let $f(v,u)$ be the number of values that appear exactly once on the edges of a simple path between vertices $v$ and $u$. Now you randomly choose $k$ vertices, which is $x_1,x_2,\dots,x_k$. For all $k=1,2,\dots,n$, calculate the expectation of $e_k=\sum_{i=1}^{k}\sum_{j=i+1}^{k}f(x_i,x_j)$ modulo $998244353$

Input

This problem contains multiple test cases.The first line of input contains a single integer $t (1 \leq t \leq 2 \cdot 10^{5})$---the number of test cases.The description of test cases follows. In a test, the first line contains a single integer $n$ ($2 \leq n \leq 2 \cdot 10^{5}$) --- the number of island Each of the next $n-1$ lines contains three integers $v , u$ and $x$ ($1 \leq v,u,x \leq n$) --- This means that this egde connects $u$ and $v$, and the value of this edge is $x$. It's guarantee the sum of $n$ over all test cases doesn't exceed $10^{6}$.

Output

For each test case, print a single value $X=e_1\oplus e_2\oplus\dots \oplus e_n$, where the note $\oplus$ denotes XOR by bit.

Sample Input

2
2
1 2 1
3
1 2 1
1 3 2

Sample Output

1
332748115

Source

2023“钉耙编程”中国大学生算法设计超级联赛（4）