Expectation

Problem Description

You are given an undirected graph consisting of $n$ vertices with $m$ weighted edges. We define the weight of a spanning tree as the bitwise AND of all edges' weight in spanning tree. Now select a spanning tree randomly, you should calculate the expected value of the weight of this spanning tree. You are required to print the result mod $998244353$. $i.e.$, print $x \times y^{-1}$ mod $998244353$ where $x \times y ^ {-1}$ is the irreducible fraction representation of the result, where $y ^ {-1}$ denotes the multiplicative inverse of $y$ modulo $998244353$.

Input

The first line is an integer $t(1 \leq t \leq 10)$, the number of test cases. For each test case, there are two space-separated integers $n(2 \leq n \leq 100)$ and $m(1 \leq m ≤ 10^{4})$ in the first line, the number of nodes and the number of edges. Then follows $m$ lines, each contains three integers $u, v, w(1 \leq u, v, \leq n, 1 \leq w \leq 10^{9}, u \neq v)$, space separated, denoting an weight edge between $u$ and $v$ has weight $w$.

Output

For each test case, output a single line with a single integer, denoting the answer.

Sample Input

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

Sample Output

1

Source

2020 Multi-University Training Contest 6