Bạn được cho một đồ thị vô hướng không có khuyên và không có cạnh đa.

Hãy tìm số cách ghi các số nguyên trong đoạn $[0; 4]$ lên các cạnh sao cho với mỗi đỉnh, tổng trọng số của các cạnh kề với đỉnh đó chia hết cho 5 (tức là bằng $5k$ với một số nguyên $k$ nào đó).

Vì kết quả có thể rất lớn, bạn chỉ cần tìm kết quả theo modulo $998\,244\,353$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên $t$ ($1 \le t \le 500\,000$): số lượng bộ dữ liệu.

Các dòng tiếp theo chứa $t$ mô tả cho các bộ dữ liệu.

Dòng đầu tiên của mỗi bộ dữ liệu chứa hai số nguyên $n, m$ ($1 \le n \le 200\,000, 0 \le m \le 300\,000$): số lượng đỉnh.

$m$ dòng tiếp theo chứa mô tả các cạnh, trong đó dòng thứ $i$ chứa hai số nguyên $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$), biểu thị một cạnh nối giữa hai đỉnh $a_i$ và $b_i$ trong đồ thị.

Đảm bảo rằng không có cạnh đa.

Cũng đảm bảo rằng tổng của $n + m$ trong tất cả các bộ dữ liệu không vượt quá $500\,000$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một số nguyên duy nhất: số cách ghi các số nguyên trong đoạn $[0; 4]$ lên các cạnh sao cho với mỗi đỉnh, tổng trọng số của các cạnh kề với đỉnh đó chia hết cho 5, theo modulo $998\,244\,353$.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1
1
5