Nota la definizione insolita di sottoalbero e diametro in questo problema.

Ecco alcune definizioni:

• La dimensione di un albero $T$ è il numero di vertici in esso contenuti, ovvero $|V(T)|$.
• Il grado di un vertice $i$ nell'albero $T$ è il numero di archi ad esso connessi, indicato con $\operatorname{deg}_i$.
• Un albero $T'$ è un sottoalbero dell'albero $T$ se e solo se:
  • Per tutti i vertici $v \in V(T')$, vale $v \in V(T)$.
  • Per tutti gli archi $e \in E(T')$, vale $e \in E(T)$.
• Sia $S_T$ l'insieme dei sottoalberi di $T$.
• Il diametro di un albero $T$ è la dimensione del più grande sottoalbero di $T$ tale che nel sottoalbero valga $\max(\operatorname{deg}_i) \le 2$.
• Sia $R_x$ l'insieme dei più grandi alberi tali che:
  • $\max(\operatorname{deg}_i) \le 3$.
  • Il diametro dell'albero sia $2x$.
• Per un albero $T$, sia $f(T)$ il più grande $k$ tale che $S_T \cap R_k \ne \emptyset$. Se non esiste un tale $k$, $f(T) = 0$.

Ti viene dato un albero $T$ con $n$ nodi. Calcola la somma di $f(T')$ per tutti i sottoalberi $T'$ di $T$ modulo $998244353$. Due sottoalberi sono diversi se e solo se hanno un diverso insieme di vertici o un diverso insieme di archi.

Input

Ogni test contiene più casi di test. La prima riga contiene un intero $t$ ($1 \le t \le 5 \times 10^4$), che indica il numero di casi di test. Segue la descrizione dei casi di test.

La prima riga contiene un intero $n$ ($1 \le n \le 10^5$, $\sum n \le 10^6$), che indica il numero di vertici nell'albero $T$.

Ciascuna delle seguenti $n - 1$ righe contiene due interi $u, v$ ($1 \le u \ne v \le n$), che indicano un arco sull'albero $T$.

Output

Per ogni caso di test, stampa un intero, che indica la somma di $f(T')$, modulo $998244353$.

Esempio

Input

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

Output

12
94

Note

Per il primo caso di test, ci sono 17 sottoalberi diversi. 5 dei sottoalberi contengono un solo vertice e quindi $f(T') = 0$. Tutti gli altri sottoalberi soddisfano $f(T') = 1$. Pertanto, la risposta è 12.