Dany jest graf nieskierowany bez pętli i krawędzi wielokrotnych.

Znajdź liczbę sposobów przypisania liczb całkowitych z przedziału $[0; 4]$ do krawędzi grafu w taki sposób, aby dla każdego wierzchołka suma wag krawędzi incydentnych do niego była równa zero modulo pięć (tj. była równa $5k$ dla pewnej liczby całkowitej $k$).

Ponieważ wynik może być bardzo duży, należy go podać modulo $998\,244\,353$.

Wejście

Pierwsza linia wejścia zawiera jedną liczbę całkowitą $t$ ($1 \le t \le 500\,000$): liczbę zestawów danych.

Kolejne linie zawierają opisy zestawów danych.

Pierwsza linia każdego zestawu danych zawiera dwie liczby całkowite $n, m$ ($1 \le n \le 200\,000, 0 \le m \le 300\,000$): liczbę wierzchołków oraz liczbę krawędzi.

Następne $m$ linii zawiera opisy krawędzi, gdzie $i$-ta z nich zawiera dwie liczby całkowite $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$), oznaczające krawędź łączącą wierzchołki $a_i$ oraz $b_i$ w grafie.

Gwarantuje się, że w grafie nie ma krawędzi wielokrotnych.

Gwarantuje się również, że łączna suma $n + m$ we wszystkich zestawach danych wynosi co najwyżej $500\,000$.

Wyjście

Dla każdego zestawu danych wypisz jedną liczbę całkowitą: liczbę sposobów przypisania liczb całkowitych z przedziału $[0; 4]$ do krawędzi tak, aby dla każdego wierzchołka suma wag krawędzi incydentnych do niego była równa zero modulo pięć, obliczoną modulo $998\,244\,353$.

Przykład

Wejście 1

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

Wyjście 1

1
1
5