Дан неориентированный граф без петель и кратных ребер.

Найдите количество способов расставить целые числа из диапазона $[0; 4]$ на ребрах так, чтобы для каждой вершины сумма весов инцидентных ей ребер была равна нулю по модулю пять (то есть была равна $5k$ для некоторого целого числа $k$).

Так как ответ может быть очень большим, выведите его по модулю $998\,244\,353$.

Входные данные

Первая строка входных данных содержит одно целое число $t$ ($1 \le t \le 500\,000$): количество тестов.

Далее следуют описания $t$ тестов.

Первая строка каждого теста содержит два целых числа $n, m$ ($1 \le n \le 200\,000, 0 \le m \le 300\,000$): количество вершин.

Следующие $m$ строк содержат описания ребер, где $i$-я из них содержит два целых числа $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$), обозначающих ребро, соединяющее вершины $a_i$ и $b_i$ в графе.

Гарантируется, что в графе нет кратных ребер.

Также гарантируется, что суммарное значение $n + m$ по всем тестам не превышает $500\,000$.

Выходные данные

Для каждого теста выведите одно целое число: количество способов расставить целые числа из диапазона $[0; 4]$ на ребрах так, чтобы для каждой вершины сумма весов инцидентных ей ребер была равна нулю по модулю пять, по модулю $998\,244\,353$.

Примеры

Входные данные 1

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

Выходные данные 1

1
1
5