Зверніть увагу на незвичне визначення піддерева та діаметра в цій задачі.

Ось деякі визначення:

• Розмір дерева $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.