I. Remove Colors
time limit per test
5 s
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree, consisting of $$$n$$$ vertices. Every vertex has a color: vertex $$$i$$$ is colored $$$a_i$$$.

In one operation, you can choose some colors (possibly, just one or all of them) and remove all vertices of all chosen colors. The edges incident to at least one removed vertex also get removed. The cost of the operation is $$$k \cdot c$$$, where $$$k$$$ is the number of chosen colors and $$$c$$$ is the number of removed vertices.

The operation can only be applied if the following condition holds: after the operation, no two vertices of the same color belong to different connected components.

What's the minimum total cost of operations required to remove the entire tree?

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 5 \cdot 10^5$$$) — the number of vertices of the tree.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the colors of the vertices.

Each of the next $$$n - 1$$$ lines contain two integers $$$v$$$ and $$$u$$$ ($$$1 \le v, u \le n$$$) — the edges of the tree.

Additional constraints on the input: the sum of $$$n$$$ over all test cases doesn't exceed $$$5 \cdot 10^5$$$, the given edges form a valid tree.

Output

For each test case, print a single integer — the minimum total cost of operations required to remove the entire tree.

Example
Input
4
3
1 1 2
1 2
2 3
3
3 1 2
1 3
3 2
4
1 2 1 2
1 2
2 3
3 4
10
4 5 1 3 5 2 3 3 1 4
5 1
2 10
3 7
6 8
9 8
9 5
5 7
4 6
10 5
Output
3
3
8
19