שימו לב להגדרה הלא שגרתית של תת-עץ וקוטר בבעיה זו.

להלן מספר הגדרות:

• הגודל של עץ $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.