Perhatikan definisi upapohon (subtree) dan diameter yang tidak biasa pada soal ini.

Berikut adalah beberapa definisi:

• Ukuran dari sebuah pohon $T$ adalah banyaknya simpul di dalamnya, yaitu $|V(T)|$.
• Derajat dari sebuah simpul $i$ pada pohon $T$ adalah banyaknya sisi yang terhubung dengannya, dinotasikan dengan $\operatorname{deg}_i$.
• Sebuah pohon $T'$ adalah upapohon dari pohon $T$ jika dan hanya jika:
  • Untuk semua simpul $v \in V(T')$, berlaku $v \in V(T)$.
  • Untuk semua sisi $e \in E(T')$, berlaku $e \in E(T)$.
• Misalkan $S_T$ adalah himpunan semua upapohon dari $T$.
• Diameter dari sebuah pohon $T$ adalah ukuran dari upapohon terbesar dari $T$ sedemikian sehingga $\max(\operatorname{deg}_i) \le 2$ di dalam upapohon tersebut.
• Misalkan $R_x$ adalah himpunan pohon-pohon terbesar sedemikian sehingga:
  • $\max(\operatorname{deg}_i) \le 3$.
  • Diameter dari pohon tersebut adalah $2x$.
• Untuk sebuah pohon $T$, misalkan $f(T)$ adalah nilai $k$ terbesar sedemikian sehingga $S_T \cap R_k \ne \emptyset$. Jika tidak ada $k$ yang demikian, maka $f(T) = 0$.

Anda diberikan sebuah pohon $T$ dengan $n$ simpul. Hitunglah jumlah dari $f(T')$ untuk semua upapohon $T'$ dari $T$ modulo $998244353$. Dua upapohon dikatakan berbeda jika dan hanya jika keduanya memiliki himpunan simpul atau himpunan sisi yang berbeda.

Masukan

Setiap pengujian berisi beberapa kasus uji. Baris pertama berisi satu bilangan bulat $t$ ($1 \le t \le 5 \times 10^4$), yang menyatakan banyaknya kasus uji. Deskripsi dari masing-masing kasus uji menyusul.

Baris pertama berisi satu bilangan bulat $n$ ($1 \le n \le 10^5$, $\sum n \le 10^6$), yang menyatakan banyaknya simpul pada pohon $T$.

Masing-masing dari $n - 1$ baris berikutnya berisi dua bilangan bulat $u, v$ ($1 \le u \ne v \le n$), yang menyatakan sebuah sisi pada pohon $T$.

Keluaran

Untuk setiap kasus uji, cetak satu bilangan bulat yang menyatakan jumlah dari $f(T')$ modulo $998244353$.

Contoh

Masukan

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

Keluaran

12
94

Catatan

Untuk kasus uji pertama, terdapat 17 upapohon berbeda. 5 dari upapohon tersebut hanya memuat satu simpul sehingga $f(T') = 0$. Semua upapohon lainnya memenuhi $f(T') = 1$. Dengan demikian, jawabannya adalah 12.