Бұл есептегі ішкі ағаш пен диаметрдің әдеттен тыс анықтамасына назар аударыңыз.

Міне, кейбір анықтамалар:

• $T$ ағашының өлшемі — ондағы төбелер саны, яғни $|V(T)|$.
• $T$ ағашындағы $i$ төбесінің дәрежесі — оған жалғанған қабырғалар саны, $\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$ ағашының диаметрі — ішкі ағашта $\max(\operatorname{deg}_i) \le 2$ шарты орындалатындай $T$ ағашының ең үлкен ішкі ағашының өлшемі.
• $R_x$ арқылы келесі шарттарды қанағаттандыратын ең үлкен ағаштар жиынын белгілейік:
  • $\max(\operatorname{deg}_i) \le 3$.
  • Ағаштың диаметрі $2x$-ке тең.
• $T$ ағашы үшін $f(T)$ — $S_T \cap R_k \ne \emptyset$ шарты орындалатын ең үлкен $k$ болсын. Егер мұндай $k$ табылмаса, $f(T) = 0$.

Сізге $n$ төбесі бар $T$ ағашы берілген. $T$ ағашының барлық $T'$ ішкі ағаштары бойынша $f(T')$ мәндерінің қосындысын $998244353$ модулі бойынша есептеңіз. Екі ішкі ағаштың төбелер жиыны немесе қабырғалар жиыны әртүрлі болса және тек сонда ғана олар әртүрлі болып саналады.

Кіріс деректер

Әрбір тест бірнеше тест жағдайларынан тұрады. Бірінші жолда тест жағдайларының санын білдіретін бір бүтін сан $t$ ($1 \le t \le 5 \times 10^4$) берілген. Одан кейін тест жағдайларының сипаттамасы беріледі.

Бірінші жолда $T$ ағашындағы төбелер санын білдіретін бір бүтін сан $n$ ($1 \le n \le 10^5$, $\sum n \le 10^6$) берілген.

Келесі $n - 1$ жолдың әрқайсысында $T$ ағашындағы қабырғаны білдіретін екі бүтін сан $u, v$ ($1 \le u \ne v \le n$) берілген.

Шығыс деректер

Әрбір тест жағдайы үшін $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.