Ti viene dato un grafo non orientato senza cappi o archi multipli.

Assegna un valore intero non negativo a ciascun vertice del grafo. Un'assegnazione è valida se soddisfa due condizioni:

• due vertici adiacenti qualsiasi hanno valori che differiscono esattamente di $1$;
• se il valore di un vertice è strettamente minore dei valori di tutti i suoi vicini, allora è uguale a $0$.

Trova il numero di assegnazioni valide modulo $998\,244\,353$. Due assegnazioni sono diverse se esiste un vertice che ha valori diversi in queste assegnazioni.

Input

La prima riga contiene un intero $t$, il numero di casi di test.

La prima riga di ogni caso di test contiene due interi $n$ e $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^6$): il numero di vertici e di archi nel grafo.

Ciascuna delle successive $m$ righe contiene due interi $u$ e $v$ ($1 \le u, v \le n$, $u \ne v$): gli estremi dell'arco corrispondente. Il grafo non contiene cappi o archi multipli. Ogni vertice ha almeno un vicino.

La somma di $m$ su tutti i casi di test non supera $10^6$.

Output

Per ogni caso di test, stampa un intero: il numero di assegnazioni valide modulo $998\,244\,353$.

Esempio

Input 1

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

Output 1

6
0