You are given a tree $T$ with $N$ nodes and the tree is rooted at node 1. Each node has a value $A[i]$ associated with it. Let us define a set $X$ as follows:

$X = \text{\{}v_1, v_2 , .... , v_k \}$ , set X has nodes $v_1, v_2, ..... ,v_k$ such that there does not exist an edge between any two vertices in $X$.

Also, $F(v)$ is the maximum value node present in the subtree of node $v$ (including itself).

$V(X)$ = $\sum_{i = 1}^{i = k} F(v_i)$ where $\{v_1, v_2 , .... ,v _ k \} \ \text{belong to X}$

Find the maximum value of $V(X)$.

Input format

• The first line contains an integer $T$ denoting the number of test cases.
• The first line of each test case contains an integer $N$ denoting the number of nodes in the tree.
• Next $N-1$ lines contain two space-separated integers denoting the edges.
• The last line contains $N$ space-separated integers denoting the value of nodes.

Output format

For each test case, print the maximum value of $F(X)$ in a new line.

Constraints

$1 \le T \le 10 \\ 1 \le N \le 10^5 \\ 1 \le A[i] \le 10^6$