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

Присвоим каждой вершине графа неотрицательное целое число. Присваивание называется корректным, если оно удовлетворяет двум условиям:

• значения любых двух соседних вершин отличаются ровно на $1$;
• если значение вершины строго меньше значений всех её соседей, то оно равно $0$.

Найдите количество корректных присваиваний по модулю $998\,244\,353$. Два присваивания считаются различными, если существует вершина, имеющая различные значения в этих присваиваниях.

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

Первая строка содержит целое число $t$ — количество наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $n$ и $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^6$) — количество вершин и рёбер в графе.

Каждая из следующих $m$ строк содержит два целых числа $u$ и $v$ ($1 \le u, v \le n$, $u \ne v$) — концы соответствующего ребра. Граф не содержит петель и кратных рёбер. У каждой вершины есть хотя бы один сосед.

Сумма $m$ по всем наборам входных данных не превосходит $10^6$.

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

Для каждого набора входных данных выведите одно целое число — количество корректных присваиваний по модулю $998\,244\,353$.

Пример

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

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

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

6
0