Vous disposez d'un graphe non orienté sans boucles ni arêtes multiples.

Trouvez le nombre de façons d'écrire des entiers dans $[0; 4]$ sur les arêtes de telle sorte que pour chaque sommet, la somme des poids des arêtes incidentes soit égale à zéro modulo cinq (c'est-à-dire égale à $5k$ pour un certain entier $k$).

Comme la réponse peut être très grande, vous devez seulement la trouver modulo $998\,244\,353$.

Entrée

La première ligne de l'entrée contient un entier $t$ ($1 \le t \le 500\,000$) : le nombre de cas de test.

Les lignes suivantes contiennent $t$ descriptions de cas de test.

La première ligne de chaque cas de test contient deux entiers $n, m$ ($1 \le n \le 200\,000, 0 \le m \le 300\,000$) : le nombre de sommets.

Les $m$ lignes suivantes contiennent les descriptions des arêtes, où la $i$-ième ligne contient deux entiers $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$), désignant une arête reliant les sommets $a_i$ et $b_i$ dans le graphe.

Il est garanti qu'il n'y a pas d'arêtes multiples.

Il est également garanti que la somme totale de $n + m$ sur tous les cas de test est au plus $500\,000$.

Sortie

Pour chaque cas de test, affichez un entier : le nombre de façons d'écrire des entiers dans $[0; 4]$ sur les arêtes de telle sorte que pour chaque sommet, la somme des poids des arêtes incidentes soit égale à zéro modulo cinq, modulo $998\,244\,353$.

Exemples

Entrée 1

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

Sortie 1

1
1
5