لاحظ التعريف غير المعتاد للشجرة الجزئية والقطر في هذه المسألة.

فيما يلي بعض التعريفات:

• حجم الشجرة $T$ هو عدد الرؤوس فيها، أي $|V(T)|$.
• درجة الرأس $i$ في الشجرة $T$ هي عدد الحواف المتصلة به، ويُرمز لها بـ $\operatorname{deg}_i$.
• تكون الشجرة $T'$ شجرة جزئية من الشجرة $T$ إذا وفقط إذا:
  • لكل الرؤوس $v \in V(T')$، يتحقق $v \in V(T)$.
  • لكل الحواف $e \in E(T')$، يتحقق $e \in E(T)$.
• لتكن $S_T$ مجموعة الأشجار الجزئية للشجرة $T$.
• قطر الشجرة $T$ هو حجم أكبر شجرة جزئية من $T$ بحيث يكون $\max(\operatorname{deg}_i) \le 2$ في تلك الشجرة الجزئية.
• لتكن $R_x$ مجموعة أكبر الأشجار التي تحقق:
  • $\max(\operatorname{deg}_i) \le 3$.
  • قطر الشجرة يساوي $2x$.
• لأي شجرة $T$، لتكن $f(T)$ هي أكبر قيمة $k$ بحيث يكون $S_T \cap R_k \ne \emptyset$. إذا لم يوجد مثل هذا $k$، فإن $f(T) = 0$.

تُعطى لك شجرة $T$ مكونة من $n$ عقدة. احسب مجموع $f(T')$ لجميع الأشجار الجزئية $T'$ من $T$ بباقي القسمة على $998244353$. تكون شجرتان جزئيتان مختلفتين إذا وفقط إذا كان لهما مجموعة رؤوس مختلفة أو مجموعة حواف مختلفة.

الإدخال

يحتوي كل اختبار على عدة حالات اختبار. يحتوي السطر الأول على عدد صحيح واحد $t$ ($1 \le t \le 5 \times 10^4$)، يشير إلى عدد حالات الاختبار. يلي ذلك وصف حالات الاختبار.

يحتوي السطر الأول من كل حالة على عدد صحيح واحد $n$ ($1 \le n \le 10^5$، $\sum n \le 10^6$)، يشير إلى عدد الرؤوس في الشجرة $T$.

يحتوي كل سطر من الأسطر الـ $n - 1$ التالية على عددين صحيحين $u, v$ ($1 \le u \ne v \le n$)، يشيران إلى حافة في الشجرة $T$.

الإخراج

لكل حالة اختبار، اطبع عدداً صحيحاً واحداً يشير إلى مجموع $f(T')$ بباقي القسمة على $998244353$.

مثال

الإدخال

2
5
1 2
1 3
2 4
2 5
8
1 2
8 7
1 3
8 6
1 4
8 5
1 8

الإخراج

12
94

ملاحظة

بالنسبة لحالة الاختبار الأولى، هناك 17 شجرة جزئية مختلفة. تحتوي 5 من الأشجار الجزئية على رأس واحد فقط وبالتالي $f(T') = 0$. جميع الأشجار الجزئية الأخرى تحقق $f(T') = 1$. وبذلك تكون الإجابة 12.