In Wonderland, there are N cities (enumerated from 1 to N) connected by $N-1$ bidirectional roads. Every city has an associated happiness score $H[i]$ related to it.
Mike starts from the capital city, $City \; 1$, and can only travel from $City \; U$ to $City \; V$, if the two cities are directly connected through a road. The happiness of the city, $H[i]$, is added to Mike's own happiness when he travels through the city. He can skip any number of cities while traveling, but that would reset his happiness to 0 (that is, when Mike skips some city, his happiness is set back to 0). Once visited or skipped, he would not be able to visit or skip that city again. Mike wants to find the maximum happiness that can be achieved during his tour. Initially, Mike's happiness is zero.
Your task is to calculate the maximum happiness that Mike can achieve during his tour.

Input Format

The first line contains an integer T, denoting the number of test cases.
For each testcase :
The first line contains an integer N, denoting the number of cities.
The second line contains N space-separated integers, the i-th of which is $H[i]$, denoting city $i$ has happiness score $H[i]$.
The third line contains M, the number of roads.
The fourth and fifth lines contain $N-1$ space-separated integers, the $i^{th}$ of which is $U[i]$ and $V[i]$ respectively. They denote that there is a bidirectional road between $City \; U$ and $City \; V$.

Input Constraints

$1 \le T \le 10$
$1 \le N \le 10^{5}$
$-10^{9} \le H[i] \le 10^{9}$
$1 \le U , V \le N$
$M = N-1$
It is guaranteed that any city can be reached from any other city.

Output Format

For each test case, print the maximum amount of happiness that Mike can achieve.
Answer for each test case should come in a new line.