K. Urban Horizons
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Theo recently downloaded a new game: Urban Horizons! In this game, he is tasked with designing a city's building layout, public transport, infrastructure, and much more. He's designed several hubs for his city, but he wants to add a highway system that connects all of these hubs. A highway connects two hubs of the city and can be traversed bidirectionally. Note that two hubs can have multiple highways between them, and a highway can connect a hub back to itself. Typically, people try to design their city's infrastructure to be as efficient as possible, but Theo is quite bad at the game. He decides that the best approach is to randomly generate highways and add them to the city. Before he enacts his plan, he first writes a simulation to test how feasible it is.

void build(Graph g) {
    int n = g.size();
    while(g.not_connected()) {
        int u = rand(1, n);
        int v = rand(1, n);
        g.add_edge(u, v);
    }
}

The code above denotes the strategy Theo uses to build the graph of highways for his city. The "not_connected" function returns true if there exists some pair of nodes that are not yet connected through some subset of edges, and the "add_edge" function adds a new edge between nodes $$$u$$$ and $$$v$$$. The function "rand(x, y)" returns a uniformly random number between $$$x$$$ and $$$y$$$, inclusive.

Theo has several different initial highway configurations he has already created on the same layout of hubs. For each initial configuration, Theo has asked you to compute the expected number of highways that need to be added to the city such that all hubs are connected directly or indirectly to each other.

Input

The first line of input consists of two integers $$$c$$$ ($$$1 \leq c \leq 100$$$) and $$$n$$$ ($$$1 \leq n \leq 22$$$) — the number of initial highway configurations to process and the number of hubs in the city.

The first line of each initial configuration consists of a single integer $$$m$$$ ($$$0 \leq m \leq 250$$$) — the number of highways that already exist in the city.

The following $$$m$$$ lines consist of two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$) — denoting the $$$i$$$th highway which connects hub $$$u_i$$$ and $$$v_i$$$.

Output

Output a line consisting of the expected number of highways that need to be added such that every hub is connected. It can be shown that the answer can be represented as $$$\frac{p}{q}$$$ where $$$p$$$ and $$$q$$$ are integers, so print the answer in the form of $$$p \cdot q^{-1} \mod 998244353$$$.

Example
Input
2 6
6
1 2
2 3
3 1
4 5
5 6
6 5
1
3 3
Output
2
891588784
Note

In the first configuration, there are two disjoint cycles of highways, each with 3 hubs. Of the 36 potential choices for $$$u$$$ and $$$v$$$, 18 of them connect the two cycles, making the graph connected. Any other choice either corresponds to a self-loop or an edge that already exists. Thus, the probability we first connect the graph after $$$k-1$$$ edges have been added is equal to $$$\frac{1}{2^k}$$$. Therefore, the expected number of edges we must add to connect the graph is equal to $$$\sum_{k=1}^{\infty} \frac{k}{2^k} = 2$$$.