给定一个无自环、无重边的无向图。

为图中的每个顶点赋予一个非负整数权值。如果一种赋值方案满足以下两个条件，则称其为合法的：

• 任意两个相邻顶点的权值恰好相差 $1$；
• 如果某个顶点的权值严格小于其所有邻居的权值，则它的权值等于 $0$。

求合法赋值方案的数量，对 $998\,244\,353$ 取模。如果存在某个顶点在两种赋值方案中的权值不同，则认为这两种赋值方案不同。

输入格式

第一行包含一个整数 $t$，表示测试数据的组数。

每组测试数据的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 10^6$，$1 \le m \le 10^6$），分别表示图中的顶点数和边数。

接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \ne v$），表示对应边的两个端点。图中不包含自环或重边。每个顶点至少有一个邻居。

所有测试数据中 $m$ 的总和不超过 $10^6$。

输出格式

对于每组测试数据，输出一个整数，表示合法赋值方案的数量对 $998\,244\,353$ 取模的结果。

样例

输入格式 1

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

输出格式 1

6
0