给定一个无向图，图中没有自环和重边。 求有多少种方案给每条边分配一个 $[0, 4]$ 之间的整数，使得对于每个顶点，与其关联的边的权值之和模 5 等于 0（即等于某个整数 $5k$）。 由于答案可能非常大，你只需要输出其对 $998\,244\,353$ 取模的结果。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 500\,000$)：测试用例的数量。 接下来包含 $t$ 个测试用例的描述。 每个测试用例的第一行包含两个整数 $n, m$ ($1 \le n \le 200\,000, 0 \le m \le 300\,000$)：顶点数。 接下来的 $m$ 行包含边的描述，其中第 $i$ 行包含两个整数 $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$)，表示图中连接顶点 $a_i$ 和 $b_i$ 的一条边。 保证图中没有重边。 同时保证所有测试用例中 $n + m$ 的总和不超过 $500\,000$。

输出格式

对于每个测试用例，输出一个整数：满足对于每个顶点，与其关联的边的权值之和模 5 等于 0（即等于某个整数 $5k$）的分配方案数，结果对 $998\,244\,353$ 取模。

样例

输入 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