自己ループや多重辺を含まない無向グラフが与えられます。

グラフの各頂点に非負整数の値を割り当てます。割り当てが次の2つの条件を満たすとき、その割り当ては有効であるといいます：

• 隣接する任意の2つの頂点の値の差がちょうど $1$ である。
• ある頂点の値がそのすべての隣接頂点の値より真に小さい場合、その値は $0$ に等しい。

有効な割り当ての個数を $998\,244\,353$ で割った余りを求めてください。2つの割り当ては、値が異なる頂点が少なくとも1つ存在するときに異なるとみなされます。

入力形式

1行目には、テストケースの個数を表す整数 $t$ が与えられます。

各テストケースの1行目には、グラフの頂点数と辺数を表す2つの整数 $n$ と $m$（$2 \le n \le 10^6$, $1 \le m \le 10^6$）が与えられます。

続く $m$ 行のそれぞれには、対応する辺の両端点を表す2つの整数 $u$ と $v$（$1 \le u, v \le n$, $u \ne v$）が与えられます。グラフは自己ループや多重辺を含みません。すべての頂点には少なくとも1つの隣接頂点が存在します。

すべてのテストケースにおける $m$ の総和は $10^6$ を超えません。

出力形式

各テストケースについて、有効な割り当ての個数を $998\,244\,353$ で割った余りを表す1つの整数を出力してください。

入出力例

入力例 1

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

出力例 1

6
0