Ниже приведены нестандартные определения поддерева и диаметра, используемые в этой задаче.

Ниже даны несколько определений.

• Размером дерева $T$ называется количество его вершин, то есть $|V(T)|$.
• Степенью вершины $i$ в дереве $T$ называется количество инцидентных ей рёбер; обозначается $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(deg_i) \le 2$.
• Пусть $R_k$ — множество всех максимальных деревьев, удовлетворяющих следующим условиям:
  • $\max(deg_i) \le 3$.
  • Диаметр дерева равен $2k$.
• Для дерева $T$ определим $f(T)$ как наибольшее целое число $k$, такое что $S_T \cap R_k \neq \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 \neq v \le n$) — рёбра дерева $T$.

Выходные данные

Для каждого тестового случая выведите целое число — остаток от деления суммы $f(T')$ на $998244353$.

Примеры

Входные данные 1

2
5
1 2
1 3
2 4
2 5
8
1 2
1 3
2 4
2 5
8 7
1 3
8 6
1 4
8 5
1 8

Выходные данные 1

12
94

Примечание

В первом тестовом случае существует 17 различных поддеревьев. Из них 5 поддеревьев содержат только одну вершину, поэтому $f(T') = 0$. Все остальные поддеревья удовлетворяют $f(T') = 1$. Следовательно, ответ равен 12.