给定一棵包含 $n$ 个顶点和 $n-1$ 条边的加权树，每条边都有一个权值。设 $f(v, u)$ 为顶点 $v$ 和 $u$ 之间的简单路径上，权值恰好出现一次的边的数量。

现在你随机选择 $k$ 个顶点，记为 $x_1, x_2, \dots, x_k$。对于所有 $k = 1, 2, \dots, n$，计算 $e_k = \sum_{i=1}^{k} \sum_{j=i+1}^{k} f(x_i, x_j)$ 的期望值，结果对 $998244353$ 取模。

输入格式

输入包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 2 \cdot 10^5$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$)，表示岛屿的数量。 接下来的 $n-1$ 行，每行包含三个整数 $v, u$ 和 $x$ ($1 \le v, u, x \le n$)，表示该边连接 $u$ 和 $v$，且该边的权值为 $x$。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出一个值 $X = e_1 \oplus e_2 \oplus \dots \oplus e_n$，其中 $\oplus$ 表示按位异或运算。

样例

样例输入 1

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

样例输出 1

1
332748115