Du får en urettet graf uten løkker eller multiple kanter.

Tilordne en ikke-negativ heltallsverdi til hver node i grafen. En tilordning er gyldig hvis den oppfyller to betingelser:

• enhver to nabonoder har verdier som har en differanse på nøyaktig $1$;
• hvis verdien til en node er strengt mindre enn verdiene til alle naboene dens, så er den lik $0$.

Finn antall gyldige tilordninger modulo $998\,244\,353$. To tilordninger er forskjellige hvis det finnes en node som har ulike verdier i disse tilordningene.

Inndata

Den første linjen inneholder et heltall $t$, antallet testtilfeller.

Den første linjen i hvert testtilfelle inneholder to heltall $n$ og $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^6$): antallet noder og kanter i grafen.

Hver av de neste $m$ linjene inneholder to heltall $u$ og $v$ ($1 \le u, v \le n$, $u \ne v$): endepunktene til den tilsvarende kanten. Grafen inneholder ikke løkker eller multiple kanter. Hver node har minst én nabo.

Summen av $m$ over alle testtilfeller overstiger ikke $10^6$.

Utdata

For hvert testtilfelle skal du skrive ut ett heltall: antall gyldige tilordninger modulo $998\,244\,353$.

Eksempel

Inndata 1

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

Utdata 1

6
0