โปรดสังเกตนิยามที่ไม่ปกติของต้นไม้ย่อย (subtree) และเส้นผ่านศูนย์กลาง (diameter) ในปัญหานี้

ต่อไปนี้คือนิยามบางประการ:

• ขนาดของต้นไม้ $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