Shuishui 有一棵包含 $n$ 个顶点的有根树，顶点编号为 $1$ 到 $n$，其中顶点 $1$ 为根。第 $i$ 个顶点的权值为 $a_i$。

现在我们从根节点开始进行深度优先搜索。由于节点的子节点可以以任意顺序遍历，因此存在多种可能的深度优先搜索序列。我们定义一个深度优先搜索序列的权值为该序列中出现在偶数下标位置的顶点的权值之和。Shuishui 想知道，在给定树的所有可能的深度优先搜索序列中，最大的权值是多少。

以下是树的深度优先搜索伪代码。调用 main() 后，dfs_order 将成为深度优先搜索序列。

Algorithm 1 An implementation of depth-first search
1: procedure dfs(vertex x)
2: Append x to the end of dfs_order
3: for each son y of x do  ▷ Sons can be iterated in arbitrary order.
4: dfs(y)
5: procedure main()
6: Let dfs_order be a global variable
7: dfs_order ← empty list
8: dfs(1)

以下是计算深度优先搜索序列权值的伪代码。调用 calc(dfs_order) 将返回其权值。

Algorithm 2 An implementation of calculating the value of a depth-first order
1: procedure calc(dfs_order)  ▷ dfs_order is a 1-based array of length n
2: s ← 0
3: p ← 2
4: while p ≤ n do
5: u ← dfs_order_p
6: s ← s + a_u
7: p ← p + 2
8: return s

输入格式

输入包含多个测试用例。 第一行包含一个整数 $t$ ($1 \le t \le 2 \times 10^5$)，表示测试用例的数量。 对于每个测试用例： 第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^5$)，表示树的顶点数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)，表示这些顶点的权值。 接下来的 $n - 1$ 行，每行包含两个整数 $u_i, v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，表示树的一条边。 保证给定的边构成一棵树。 保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出一行一个整数，表示答案。

样例

输入 1

3
2
1 2
1 2
4
1 1 222 222
1 2
1 3
2 4
6
1 5 4 6 1 1
6 1
4 5
4 2
1 4
1 3

输出 1

2
444
15

说明

在样例的第一个测试用例中，dfs_order 是唯一的，即 $[1, 2]$，其权值为 $a_2 = 2$。注意 dfs_order 是从 $1$ 开始计数的。

在样例的第二个测试用例中，权值最大的 dfs_order 为 $[1, 3, 2, 4]$，其权值为 $a_3 + a_4 = 444$。