Anda diberikan sebuah graf tak berarah tanpa gelung (self-loop) maupun sisi ganda (multiple edges).

Berikan sebuah nilai bilangan bulat tak negatif pada setiap simpul graf tersebut. Suatu penugasan dikatakan valid jika memenuhi dua syarat berikut:

• setiap dua simpul yang bertetangga memiliki nilai yang berselisih tepat $1$;
• jika nilai suatu simpul lebih kecil secara tegas daripada nilai semua tetangganya, maka nilainya sama dengan $0$.

Carilah banyaknya penugasan yang valid modulo $998\,244\,353$. Dua penugasan dianggap berbeda jika terdapat suatu simpul yang memiliki nilai berbeda pada kedua penugasan tersebut.

Format Masukan

Baris pertama berisi sebuah bilangan bulat $t$, yaitu banyaknya kasus uji.

Baris pertama pada setiap kasus uji berisi dua bilangan bulat $n$ dan $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^6$): banyaknya simpul dan sisi pada graf.

Masing-masing dari $m$ baris berikutnya berisi dua bilangan bulat $u$ dan $v$ ($1 \le u, v \le n$, $u \ne v$): titik-titik ujung dari sisi yang bersesuaian. Graf tidak memuat gelung maupun sisi ganda. Setiap simpul memiliki setidaknya satu tetangga.

Jumlah nilai $m$ di seluruh kasus uji tidak melebihi $10^6$.

Format Keluaran

Untuk setiap kasus uji, keluarkan satu bilangan bulat: banyaknya penugasan yang valid modulo $998\,244\,353$.

Contoh

Format Masukan 1

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

Format Keluaran 1

6
0