Yukikaze 热爱图论，尤其是森林和独立集。

• 森林：一个无环的无向图。
• 独立集：图中的一个顶点子集，使得其中任意两个顶点之间都没有边相连。

Yukikaze 有一个无向图 $G = (V, E)$，其中 $V$ 是顶点集，$E$ 是边集。每个顶点 $v \in V$ 都有一个权值。现在她想把 $V$ 分成两个互补的子集 $V_I$ 和 $V_F$，使得 $V_I$ 是一个独立集，且导出子图 $G[V_F]$ 是一片森林。导出子图 $G[V_F]$ 是指顶点集为 $V_F$，且边集由所有两个端点都在 $V_F$ 中的 $E$ 中的边组成的图。此外，她希望最大化 $V_I$ 中顶点的权值之和。

由于这个问题对于一般图是 NP-hard 的，她决定解决该问题的一个特殊情况。我们可以通过以下步骤构建一个特殊的图：初始时，图包含三个顶点 $1, 2, 3$ 以及三条边 $(1, 2), (2, 3), (3, 1)$。当我们向图中添加一个顶点 $x$ 时，我们选择图中已存在的一条边 $(y, z)$，并连接 $(x, y)$ 和 $(x, z)$。不断重复此过程，直到图中共有 $n$ 个顶点。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^3$)，表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$ ($4 \le n \le 10^5$)，表示图中的顶点数。保证所有测试用例的 $n$ 之和不超过 $10^6$。 每个测试用例的第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)，表示顶点的权值。 初始时，图包含三个顶点 $1, 2, 3$ 以及三条边 $(1, 2), (2, 3), (3, 1)$。接下来的 $n - 3$ 行中，第 $i$ 行包含两个整数 $u, v$ ($1 \le u, v < i + 3$)，表示添加一个顶点 $i + 3$ 以及两条边 $(i + 3, u), (i + 3, v)$ 到图中。保证 $(u, v)$ 在图中已经存在。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示 $V_I$ 中顶点权值的最大和。

样例

样例输入 1

3
4
3 3 2 2
1 2
4
2 5 5 2
2 3
5
3 1 1 1 1
1 2
1 3

样例输出 1

4
5
3