Дано некорневое дерево, содержащее $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