يُعطى لك رسم بياني غير موجه بدون حلقات ذاتية أو حواف متعددة.

عيّن قيمة صحيحة غير سالبة لكل رأس في الرسم البياني. يكون التعيين صالحًا إذا حقق شرطين:

• أي رأسين متجاورين لهما قيمتان تختلفان بمقدار $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