Cho một cây không gốc gồm $n$ đỉnh, trong đó mỗi đỉnh có một màu được biểu diễn bởi số nguyên dương $c_i$ đối với đỉnh thứ $i$.

Giả sử $S$ và $T$ là các tập hợp đỉnh trong cây. Một cặp có thứ tự $(S, T)$ được coi là hợp lệ nếu thỏa mãn tất cả các điều kiện sau:

• Cả $S$ và $T$ đều là các tập hợp khác rỗng;
• Tất cả các đỉnh trong $S$ có cùng màu, và tất cả các đỉnh trong $T$ có cùng màu;
• Đồ thị con $\text{sub}(S)$ của tập đỉnh $S$ được định nghĩa là đồ thị con liên thông nhỏ nhất của cây có chứa tập đỉnh $S$, và định nghĩa tương tự cho $\text{sub}(T)$. Yêu cầu $\text{sub}(S)$ và $\text{sub}(T)$ không giao nhau, nghĩa là chúng không có đỉnh chung hay cạnh chung nào.

Hãy xác định số lượng tất cả các cặp có thứ tự $(S, T)$ hợp lệ theo modulo $998244353$. Lưu ý rằng nếu $S \neq T$ thì cặp có thứ tự $(S, T)$ được coi là khác với cặp có thứ tự $(T, S)$.

Dữ liệu vào

Bài toán này gồm nhiều bộ dữ liệu. Dòng đầu tiên của dữ liệu vào chứa một số nguyên $T$ ($1 \le T \le 10^4$), biểu thị số lượng bộ dữ liệu.

Đối với mỗi bộ dữ liệu:

Dòng đầu tiên chứa một số nguyên $n$ ($1 \le n \le 2 \times 10^5$), biểu thị số lượng đỉnh trong cây không gốc.

Dòng thứ hai chứa $n$ số nguyên $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$), biểu thị màu của mỗi đỉnh.

Trong $n - 1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u, v$ ($1 \le u, v \le n, u \neq v$), biểu thị các cạnh của cây. Dữ liệu đảm bảo $n - 1$ cạnh này tạo thành một cấu trúc cây.

Dữ liệu đảm bảo tổng của $n$ qua tất cả các bộ dữ liệu không vượt quá $2 \times 10^5$.

Dữ liệu ra

Đối với mỗi bộ dữ liệu, in ra một dòng duy nhất chứa một số nguyên biểu thị số lượng cặp có thứ tự theo modulo $998244353$.

Ví dụ

Dữ liệu vào mẫu 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

Dữ liệu ra mẫu 1

2
54
42