Bob lives on a magical land. There are n cities and m roads on the land. The length of the i-th road is
w i , and the length is an integer between 1 and L. Each road connects two cities. The land can be viewed
as a graph of n points and m edges.
This land is magical because Bob was surprised to find that there are no simple circuits with an even
total length in this land!
Bob likes to travel. If Bob takes a simple path from x to y (x < y), the happiness value is the greatest
common factor (gcd) of the lengths of all roads on the path.
simple path:A path is called a simple path if the vertices on the path do not repeat each other.
simple circuit:A circuit in which the vertices are not repeated except for the first and last vertices is
called a simple circuit
Bob wants to count all possible travel paths.
Define F(k) as the total number of travel paths with happiness value k, modulo 998244353.
Please find F(1)xorF(2)xorF(3)...xorF(L),
输入格式
The first line contains an integer T(T ≤ 500) —the number of test cases.
The first line of each test case contains 3 integers n,m,L(1 ≤ n,L ≤ 100000,1 ≤ m ≤ 200000) —number
of cities, number of roads, length range of roads.
The next m lines , each line contains 3 integers u i ,v i ,w i (1 ≤ u i ,v i ≤ n,1 ≤ w i ≤ L) —.represents a road
of length w i connecting u i ,v i .
It is guaranteed that there are no double edges and self-loops.
1 ≤sigema（n）,sigema（L） ≤ 500000,1 ≤sigema（m） ≤ 1000000
输出格式
For each test case, output a line containing an integer representing the answer