ループや多重辺を持たない無向グラフが与えられる。各辺に $0$ から $4$ までの整数を書き込む方法のうち、各頂点について、その頂点に接続する辺の重みの和が $5$ を法として $0$ になる（すなわち、ある整数 $k$ に対して $5k$ となる）ようなものの個数を求めよ。

答えは非常に大きくなる可能性があるため、$998\,244\,353$ を法とした余りを求めればよい。

入力

入力の最初の行には、テストケースの数 $t$ ($1 \le t \le 500\,000$) が含まれる。 続く行に $t$ 個のテストケースの記述がある。 各テストケースの最初の行には、頂点数と辺数を表す2つの整数 $n, m$ ($1 \le n \le 200\,000, 0 \le m \le 300\,000$) が含まれる。 続く $m$ 行には辺の記述があり、$i$ 番目の行には頂点 $a_i$ と $b_i$ を結ぶ辺を表す2つの整数 $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$) が含まれる。

多重辺は存在しないことが保証されている。 また、すべてのテストケースにおける $n + m$ の総和は $500\,000$ 以下であることが保証されている。

出力

各テストケースについて、各頂点に接続する辺の重みの和が $5$ を法として $0$ になるように辺に $0$ から $4$ までの整数を書き込む方法の数を、$998\,244\,353$ を法として1行に出力せよ。

入出力例

入力 1

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

出力 1

1
1
5