Дано некореневе дерево, що містить $n$ вершин, де кожна вершина має колір, представлений додатним цілим числом $c_i$ для $i$-ї вершини.

Нехай $S$ і $T$ — множини вершин дерева. Впорядкована пара $(S, T)$ вважається коректною, якщо виконуються всі такі умови:

• І $S$, і $T$ є непорожніми множинами;
• Усі вершини в $S$ мають однаковий колір, і всі вершини в $T$ мають однаковий колір;
• Підграф $\text{sub}(S)$ множини вершин $S$ визначається як найменший зв'язний підграф дерева, що містить множину вершин $S$, і аналогічно для $\text{sub}(T)$. Вимагається, щоб $\text{sub}(S)$ і $\text{sub}(T)$ не перетиналися, тобто не мали спільних вершин або ребер.

Визначте кількість усіх коректних впорядкованих пар $(S, T)$ за модулем $998244353$. Слід зазначити, що якщо $S \neq T$, то впорядкована пара $(S, T)$ вважається відмінною від впорядкованої пари $(T, S)$.

Вхідні дані

Ця задача містить декілька наборів вхідних даних. Перший рядок вхідних даних містить ціле число $T$ ($1 \le T \le 10^4$), що позначає кількість наборів вхідних даних.

Для кожного набору вхідних даних:

Перший рядок містить ціле число $n$ ($1 \le n \le 2 \times 10^5$), що позначає кількість вершин у некореневому дереві.

Другий рядок містить $n$ цілих чисел $c_1, c_2, \dots, c_n$ ($1 \le c_i \le n$), що позначають колір кожної вершини.

Наступні $n - 1$ рядків містять по два цілі числа $u, v$ ($1 \le u, v \le n, u \neq v$), що позначають ребра дерева. Гарантується, що ці $n - 1$ ребер утворюють структуру дерева.

Гарантується, що загальна сума $n$ за всіма наборами вхідних даних не перевищує $2 \times 10^5$.

Вихідні дані

Для кожного набору вхідних даних виведіть один рядок, що містить ціле число — кількість впорядкованих пар за модулем $998244353$.

Приклад

Приклад вхідних даних 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

Приклад вихідних даних 1

2
54
42