Dany jest graf nieskierowany bez pętli własnych oraz krawędzi wielokrotnych.

Przypisz każdemu wierzchołkowi grafu pewną nieujemną wartość całkowitą. Przypisanie nazwiemy poprawnym, jeśli spełnia dwa warunki:

• każde dwa sąsiednie wierzchołki mają wartości różniące się dokładnie o $1$;
• jeśli wartość pewnego wierzchołka jest ściśle mniejsza od wartości wszystkich jego sąsiadów, to jest ona równa $0$.

Wyznacz liczbę poprawnych przypisań modulo $998\,244\,353$. Dwa przypisania uznajemy za różne, jeśli istnieje wierzchołek, który ma w tych przypisaniach różne wartości.

Wejście

Pierwszy wiersz zawiera liczbę całkowitą $t$, oznaczającą liczbę przypadków testowych.

Pierwszy wiersz każdego przypadku testowego zawiera dwie liczby całkowite $n$ oraz $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^6$): liczbę wierzchołków oraz liczbę krawędzi w grafie.

Każdy z kolejnych $m$ wierszy zawiera dwie liczby całkowite $u$ oraz $v$ ($1 \le u, v \le n$, $u \ne v$): końce odpowiedniej krawędzi. Graf nie zawiera pętli własnych ani krawędzi wielokrotnych. Każdy wierzchołek ma co najmniej jednego sąsiada.

Suma wartości $m$ po wszystkich przypadkach testowych nie przekracza $10^6$.

Wyjście

Dla każdego przypadku testowego wypisz jedną liczbę całkowitą: liczbę poprawnych przypisań modulo $998\,244\,353$.

Przykład

Wejście 1

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

Wyjście 1

6
0