Gegeben ist ein unbewurzelter Baum mit $n$ Knoten, wobei jeder Knoten eine Farbe hat, die für den $i$-ten Knoten durch eine positive ganze Zahl $c_i$ dargestellt wird.

Angenommen, $S$ und $T$ sind Mengen von Knoten im Baum. Ein geordnetes Paar $(S, T)$ gilt als gültig, wenn alle folgenden Bedingungen erfüllt sind:

• Sowohl $S$ als auch $T$ sind nicht-leere Mengen;
• Alle Knoten in $S$ haben dieselbe Farbe, und alle Knoten in $T$ haben dieselbe Farbe;
• Der Teilgraph $\text{sub}(S)$ der Knotenmenge $S$ ist definiert als der kleinste zusammenhängende Teilgraph des Baums, der die Knotenmenge $S$ enthält, und analog für $\text{sub}(T)$. Es wird gefordert, dass sich $\text{sub}(S)$ und $\text{sub}(T)$ nicht schneiden, d. h. sie haben keine gemeinsamen Knoten oder Kanten.

Bestimme die Anzahl aller gültigen geordneten Paare $(S, T)$ modulo $998244353$. Es ist zu beachten, dass für $S \neq T$ das geordnete Paar $(S, T)$ als verschieden vom geordneten Paar $(T, S)$ betrachtet wird.

Eingabe

Dieses Problem enthält mehrere Testfälle. Die erste Zeile der Eingabe enthält eine ganze Zahl $T$ ($1 \le T \le 10^4$), die die Anzahl der Testfälle angibt.

Für jeden Testfall:

Die erste Zeile enthält eine ganze Zahl $n$ ($1 \le n \le 2 \times 10^5$), die die Anzahl der Knoten im unbewurzelten Baum angibt.

Die zweite Zeile enthält $n$ ganze Zahlen $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$), die die Farbe jedes Knotens angeben.

Die nächsten $n - 1$ Zeilen enthalten jeweils zwei ganze Zahlen $u, v$ ($1 \le u, v \le n, u \neq v$), die die Kanten des Baums darstellen. Es ist garantiert, dass diese $n - 1$ Kanten eine Baumstruktur bilden.

Die Daten garantieren, dass die Gesamtsumme von $n$ über alle Testfälle hinweg $2 \times 10^5$ nicht überschreitet.

Ausgabe

Gib für jeden Testfall eine einzelne Zeile mit einer ganzen Zahl aus, die die Anzahl der geordneten Paare modulo $998244353$ darstellt.

Beispiel

Beispieleingabe 1

3
2
1 1
1 2
5
1 1 1 2 2
1 2
2 3
3 4
4 5
5
1 2 1 2 1
1 2
1 3
2 4
2 5

Beispielausgabe 1

2
54
42