J. Just Counting
time limit per test
1 s
memory limit per test
512 mebibytes
input
standard input
output
standard output

You are given an undirected graph without loops and multiple edges.

Find the number of ways to write integers $$$[0; 4]$$$ on edges such that for each vertex, the sum of weights of edges incident to it will be equal to zero modulo five (i.e. is equal to $$$5k$$$ for some integer $$$k$$$).

As the answer may be very large, you only need to find it modulo $$$998\,244\,353$$$.

Input

The first line of input contains one integer $$$t$$$ ($$$1 \leq t \leq 500\,000 $$$): the number of testcases.

The next lines contain $$$t$$$ descriptions of test cases.

The first line of each test case contains two integers $$$n,m$$$ ($$$1 \leq n \leq 200\,000, 0 \leq m \leq 300\,000$$$): the number of vertices.

The next $$$m$$$ lines contain descriptions of edges, where the $$$i$$$-th of them contains two integers $$$a_i, b_i$$$ ($$$1 \leq a_i, b_i \leq n, a_i \neq b_i$$$), denoting an edge connecting vertices $$$a_i$$$ and $$$b_i$$$ in the graph.

It is guaranteed that there are no multiple edges.

It is also guaranteed that the total sum of $$$n+m$$$ in all test cases is at most $$$500\,000$$$.

Output

For each test case, print one integer: the number of ways to write integers $$$[0; 4]$$$ on edges such that for each vertex, the sum of weights of edges incident to it will be equal to zero modulo five (i.e. is equal to $$$5k$$$ for some integer $$$k$$$), modulo $$$998\,244\,353$$$.

Example
Input
3
1 0
3 3
1 2
2 3
3 1
4 4
1 2
2 3
3 4
4 1
Output
1
1
5