On vous donne un graphe non orienté sans boucles ni arêtes multiples.

Attribuez une valeur entière positive ou nulle à chaque sommet du graphe. Une affectation est valide si elle satisfait deux conditions :

• deux sommets adjacents quelconques ont des valeurs qui diffèrent d'exactement $1$ ;
• si la valeur d'un sommet est strictement inférieure aux valeurs de tous ses voisins, alors elle est égale à $0$.

Trouvez le nombre d'affectations valides modulo $998\,244\,353$. Deux affectations sont différentes s'il existe un sommet qui a des valeurs différentes dans ces affectations.

Entrée

La première ligne contient un entier $t$, le nombre de cas de test.

La première ligne de chaque cas de test contient deux entiers $n$ et $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^6$) : le nombre de sommets et d'arêtes dans le graphe.

Chacune des $m$ lignes suivantes contient deux entiers $u$ et $v$ ($1 \le u, v \le n$, $u \ne v$) : les extrémités de l'arête correspondante. Le graphe ne contient ni boucles ni arêtes multiples. Chaque sommet a au moins un voisin.

La somme de $m$ sur l'ensemble des cas de test ne dépasse pas $10^6$.

Sortie

Pour chaque cas de test, affichez un entier : le nombre d'affectations valides modulo $998\,244\,353$.

Exemple

Entrée 1

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

Sortie 1

6
0