You are given an undirected graph without self-loops or multiple edges.

Assign a nonnegative integer value to each vertex of the graph. An assignment is valid if it satisfies two conditions:

• any two adjacent vertices have values that differ by exactly $1$;
• if the value of a vertex is strictly less than the values of all its neighbors, then it is equal to $0$.

Find the number of valid assignments modulo $998\,244\,353$. Two assignments are different if there exists a vertex that has different values in these assignments.

Input

The first line contains an integer $t$, the number of test cases.

The first line of each test case contains two integers $n$ and $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^6$): the number of vertices and edges in the graph.

Each of the next $m$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n$, $u \ne v$): the endpoints of the corresponding edge. The graph does not contain self-loops or multiple edges. Every vertex has at least one neighbor.

The sum of $m$ over all test cases does not exceed $10^6$.

Output

For each test case, output one integer: the number of valid assignments modulo $998\,244\,353$.

Example

Input 1

2
4 3
1 2
2 3
3 4
3 3
1 2
2 3
1 3

Output 1

6
0