給定一個無向圖，其中沒有自環與重邊。

請計算有多少種方式可以在邊上填寫 $[0; 4]$ 之間的整數，使得對於每個頂點，與其相連的邊的權重總和對 5 取模後等於 0（即等於某個整數 $k$ 的 $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$。

輸出格式

對於每組測試資料，輸出一個整數：在邊上填寫 $[0; 4]$ 之間的整數，使得每個頂點相連邊的權重總和對 5 取模後為 0 的方案數，結果對 $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