Given an unrooted tree containing $n$ nodes, where each node has a color represented by a positive integer $c_i$ for the $i$-th node.

Assume that $S$ and $T$ are sets of nodes in the tree. An ordered pair $(S, T)$ is considered valid if all the following conditions are met:

• Both $S$ and $T$ are non-empty sets;
• All nodes in $S$ have the same color, and all nodes in $T$ have the same color;
• The subgraph $\text{sub}(S)$ of the set of nodes $S$ is defined as the smallest connected subgraph of the tree that contains the set of nodes $S$, and similarly for $\text{sub}(T)$. It is required that $\text{sub}(S)$ and $\text{sub}(T)$ do not intersect, meaning they have no common nodes or edges.

Determine the number of all valid ordered pairs $(S, T)$ modulo $998244353$. It should be noted that if $S \neq T$, then the ordered pair $(S, T)$ is considered different from the ordered pair $(T, S)$.

Input

This problem contains multiple test cases. The first line of input contains an integer $T$ ($1 \le T \le 10^4$), representing the number of test cases.

For each test case:

The first line contains an integer $n$ ($1 \le n \le 2 \times 10^5$), representing the number of nodes in the unrooted tree.

The second line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$), representing the color of each node.

The next $n - 1$ lines each contain two integers $u, v$ ($1 \le u, v \le n, u \neq v$), representing the edges of the tree. It is guaranteed that these $n - 1$ edges form a tree structure.

The data guarantees that the total sum of $n$ across all test cases does not exceed $2 \times 10^5$.

Output

For each test case, output a single line containing an integer, representing the number of ordered pairs modulo $998244353$.

Example

Sample Input 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

Sample Output 1

2
54
42