Tenga en cuenta la definición inusual de subárbol y diámetro en este problema. Aquí hay algunas definiciones:

• El tamaño de un árbol $T$ es el número de vértices en él, es decir, $|V(T)|$.
• El grado de un vértice $i$ en el árbol $T$ es el número de aristas conectadas a él, denotado por $deg_i$.
• Un árbol $T'$ es un subárbol de un árbol $T$ si y solo si:
  • Para todos los vértices $v \in V(T')$, $v \in V(T)$.
  • Para todas las aristas $e \in E(T')$, $e \in E(T)$.
• Sea $S_T$ el conjunto de subárboles de $T$.
• El diámetro de un árbol $T$ es el tamaño del subárbol más grande de $T$ tal que $max(deg_i) \le 2$ en el subárbol.
• Sea $R_x$ el conjunto de los árboles más grandes tales que:
  • $max(deg_i) \le 3$.
  • El diámetro del árbol es $2x$.
• Para un árbol $T$, sea $f(T)$ el mayor $k$ tal que $S_T \cap R_k \neq \emptyset$. Si no existe tal $k$, $f(T) = 0$.

Se le da un árbol $T$ con $n$ nodos. Cuente la suma de $f(T')$ para todos los subárboles $T'$ de $T$ módulo 998244353. Dos subárboles son diferentes si y solo si tienen un conjunto de vértices o un conjunto de aristas diferente.

Entrada

Cada caso de prueba contiene múltiples casos de prueba. La primera línea contiene un entero $t$ ($1 \le t \le 5 \times 10^4$), que indica el número de casos de prueba. La descripción de los casos de prueba sigue. La primera línea contiene un entero $n$ ($1 \le n \le 10^5$, $\sum n \le 10^6$), que indica el número de vértices en el árbol $T$. Cada una de las siguientes $n-1$ líneas contiene dos enteros $u, v$ ($1 \le u \neq v \le n$), que indican una arista en el árbol $T$.

Salida

Para cada caso de prueba, imprima un entero, que indica la suma de $f(T')$, módulo 998244353.

Ejemplos

Entrada 1

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

Salida 1

12
94

Nota 1

Para el primer caso de prueba, hay 17 subárboles diferentes. 5 de los subárboles contienen solo un vértice y, por lo tanto, $f(T') = 0$. Todos los demás subárboles satisfacen $f(T') = 1$. Por lo tanto, la respuesta es 12.