派蒙在她的左口袋里发现了一棵初始时所有顶点均为白色的树，并决定玩弄它。一棵有 $(n + 1)$ 个节点的树是一个具有 $n$ 条边的无向连通图。

派蒙会给你一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$。我们首先需要选择树中的一个顶点并将其涂成黑色。然后我们执行 $n$ 次以下操作。

在第 $i$ 次操作中，我们选择一个与某个黑色顶点 $y_i$ 直接相连的白色顶点 $x_i$，将连接它们的边的权重设为 $a_i$，并将 $x_i$ 涂成黑色。在这 $n$ 次操作后，我们得到了一棵所有边都有权重的树。

如果我们最优地选择顶点，加权树直径的最大长度是多少？加权树的直径是该树中最长的简单路径。简单路径的长度是该路径上所有边的权重之和。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 5 \times 10^3$)，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 150$)，表示序列的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)，表示该序列。

接下来的 $n$ 行，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n + 1$)，表示树中存在一条连接顶点 $u_i$ 和 $v_i$ 的边。

保证满足 $n > 20$ 的测试数据不超过 10 组。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示树的直径的最大长度。

样例

样例输入 1

2
5
1 7 3 5 4
1 3
2 3
3 4
4 5
4 6
1
1000000000
1 2

样例输出 1

16
1000000000

说明

对于第一个样例测试数据，我们按 $1, 3, 4, 5, 2, 6$ 的顺序选择顶点，得到如下图所示的加权树。显然，最长的简单路径长度为 16。