The city where crazyzhk resides is structured as a tree. On a certain day, the city’s network needs to be upgraded. To achieve this goal, routers need to be deployed. Each router covers the node it is placed on and its neighboring nodes. There is a cost $a_i$ associated with placing a router at each node. The question is: How can the routers be deployed at minimum cost to ensure that every node is covered?

Input

The input consists of multiple test cases. The first line contains a single integer $t$($1 \le t \le 1000$) — the number of test cases. Description of the test cases follows.

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

The second line of each case are $n$ integers $a_i$($1 \le a_i \le 10^5$),denoting the cost of setting up a router at each node.

Each of the next $n − 1$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n, u \ne v$) meaning that there is an edge between vertices $u$ and $v$ in the tree.

The data guarantees that the sum of n will not exceed $2 \cdot 10^5$

Output

For each test case print a single integer —— the minimum cost to ensure that every node is covered

Example

2
7
13 20 1 20 6 9 8
1 2
1 3
2 4
2 5
3 6
5 7
4
1 17 13 4
1 2
1 3
3 4

27
5

Limitation

Time limit: 3 seconds

Memory limit: 128 megabytes