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

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

• значення будь-яких двох сусідніх вершин відрізняються рівно на $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