Bob 居住在一片神奇的土地上。这片土地上有 $n$ 个城市和 $m$ 条道路。第 $i$ 条道路的长度为 $w_i$，长度是 $1$ 到 $L$ 之间的整数。每条道路连接两个城市。这片土地可以看作一个有 $n$ 个点和 $m$ 条边的图。

这片土地之所以神奇，是因为 Bob 惊讶地发现，这片土地上不存在总长度为偶数的简单环！

Bob 喜欢旅行。如果 Bob 选择一条从 $x$ 到 $y$ ($x < y$) 的简单路径，其幸福值为路径上所有道路长度的最大公约数 (gcd)。

简单路径：如果路径上的顶点互不重复，则称该路径为简单路径。 简单环：除了首尾顶点外，其余顶点互不重复的环称为简单环。

Bob 想要统计所有可能的旅行路径。

定义 $F(k)$ 为幸福值为 $k$ 的旅行路径总数，对 $998244353$ 取模。 请计算 $F(1) \oplus F(2) \oplus F(3) \oplus \dots \oplus F(L)$，其中 $\oplus$ 表示异或运算。

输入格式

第一行包含一个整数 $T$ ($T \le 500$)，表示测试用例的数量。 每个测试用例的第一行包含 3 个整数 $n, m, L$ ($1 \le n, L \le 100000, 1 \le m \le 200000$)，分别表示城市数量、道路数量和道路长度范围。 接下来的 $m$ 行，每行包含 3 个整数 $u_i, v_i, w_i$ ($1 \le u_i, v_i \le n, 1 \le w_i \le L$)，表示一条连接 $u_i$ 和 $v_i$、长度为 $w_i$ 的道路。

保证图中没有重边和自环。 $1 \le \sum n, \sum L \le 500000, 1 \le \sum m \le 1000000$。

输出格式

对于每个测试用例，输出一行，包含一个表示答案的整数。

样例

输入 1

2
3 3 6
1 2 6
2 3 4
3 1 5
5 4 10
1 2 10
1 3 1
2 4 7
1 5 4

输出 1

2
6