There are n pokemons all over the world, numbered from 1 to n. We decide who can go to Galar according to the following rules.

We start with a cactus (i.e. a connected graph in which every edge belongs to at most one simple cycle) having n vertices and m bidirectional edges, where the i-th vertex represents the pokemon i and each edge has a probability to go through.

Pokemons go to Galar in rounds. In the first round, only the pokemon 1 is allowed to go to Galar. In the i-th round (), if pokemon u has got the permission to Galar in the (i - 1)-th round, pokemon v hasn't got the permission yet, and there is an edge between pokemon u and pokemon v with probability w to go through, then pokemon v will have a probability w to go to Galar in this round. If there is no pokemon that can get permission, the further rounds will be skipped. You can see the note after the sample for better understanding of this procedure.

Please calculate the expected population of pokemons that can travel to Galar. In order to avoid precision issues, output the expected value modulo 998244353. Formally, let the answer be , you need to output the minimum non-negative integer r satisfying that . For example, .

There are multiple test cases. The first line contains an integer T (), indicating the number of test cases. Test cases are given in the following.

For each test case, the first line contains two integers n, m (, ), representing the number of vertices and the number of edges in the cactus respectively.

Each of the next m lines contains four integers u, v, a, b (, , ), representing an edge between the u-th vertex and the v-th one with probability  to go through. We ensure that the given graph is a cactus with no self-loops or multiple edges.

For each test case, output "Case #x: y" in one line (without quotes), where x indicates the case number starting from 1, and y denotes the answer to this test case modulo 998244353.

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

Case #1: 499122178
Case #2: 748683267

In the second example case, there are six possible cases in total as following.

1.  with probability .
2.  with probablity .
3.  with probablity .
4.  with probablity .
5.  with probablity .
6.  with probablity .

Hence, the answer is .