Se te proporciona un grafo no dirigido sin bucles ni aristas múltiples.

Encuentra el número de formas de escribir enteros en el rango $[0; 4]$ en las aristas, de tal manera que para cada vértice, la suma de los pesos de las aristas incidentes a él sea igual a cero módulo cinco (es decir, igual a $5k$ para algún entero $k$).

Como la respuesta puede ser muy grande, solo necesitas encontrarla módulo $998\,244\,353$.

Entrada

La primera línea de la entrada contiene un entero $t$ ($1 \le t \le 500\,000$): el número de casos de prueba.

Las siguientes líneas contienen las descripciones de los $t$ casos de prueba.

La primera línea de cada caso de prueba contiene dos enteros $n, m$ ($1 \le n \le 200\,000, 0 \le m \le 300\,000$): el número de vértices.

Las siguientes $m$ líneas contienen las descripciones de las aristas, donde la $i$-ésima de ellas contiene dos enteros $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$), que denotan una arista que conecta los vértices $a_i$ y $b_i$ en el grafo.

Se garantiza que no hay aristas múltiples.

También se garantiza que la suma total de $n + m$ en todos los casos de prueba es como máximo $500\,000$.

Salida

Para cada caso de prueba, imprime un entero: el número de formas de escribir enteros en el rango $[0; 4]$ en las aristas, de tal manera que para cada vértice, la suma de los pesos de las aristas incidentes a él sea igual a cero módulo cinco (es decir, igual a $5k$ para algún entero $k$), módulo $998\,244\,353$.

Ejemplos

Entrada 1

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

Salida 1

1
1
5