Gefið er óstefnt net án sjálfslykkja eða margfaldra leggja.

Úthlutaðu hverjum hnúti netsins ekki-neikvæðu heiltölugildi. Úthlutun er gild ef hún uppfyllir tvö skilyrði:

• sérhverjir tveir aðliggjandi hnútar hafa gildi sem munar nákvæmlega um $1$;
• ef gildi hnúts er strangt minna en gildi allra nágranna hans, þá er það jafnt og $0$.

Finndu fjölda gildra úthlutana módúló $998\,244\,353$. Tvær úthlutanir eru ólíkar ef til er hnútur sem hefur ólík gildi í þessum úthlutunum.

Inntak

Fyrsta línan inniheldur heiltölu $t$, fjölda prófunartilvika.

Fyrsta lína hvers prófunartilviks inniheldur tvær heiltölur $n$ og $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^6$): fjölda hnúta og leggja í netinu.

Hver af næstu $m$ línum inniheldur tvær heiltölur $u$ og $v$ ($1 \le u, v \le n$, $u \ne v$): endapunkta samsvarandi leggs. Netið inniheldur hvorki sjálfslykkjur né margfalda leggi. Sérhver hnútur á sér að minnsta kosti einn nágranna.

Summa $m$ yfir öll prófunartilvik fer ekki yfir $10^6$.

Úttak

Fyrir hvert prófunartilvik skal prenta eina heiltölu: fjölda gildra úthlutana módúló $998\,244\,353$.

Dæmi

Inntak 1

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

Úttak 1

6
0