$n$개의 정점을 포함하는 루트 없는 트리가 주어지며, 각 정점에는 색상이 지정되어 있어 양의 정수 $c_i$가 $i$번째 정점의 색상을 나타냅니다.

$S$와 $T$를 트리의 정점 집합이라고 합시다. 다음 조건들을 모두 만족할 때 순서쌍 $(S, T)$를 올바른 순서쌍이라고 합니다:

• $S$와 $T$는 모두 공집합이 아니다;
• $S$에 속한 모든 정점의 색상이 같고, $T$에 속한 모든 정점의 색상이 같다;
• 정점 집합 $S$의 부분 그래프 $\text{sub}(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