Problem Description

对于一棵每个点都有点权的树，我们可以定义这棵树$T$的价值为$T_{min}\times T_{max}$，其中$T_{min}$为树上点权最小的点，$T_{max}$为树上点权最大的点。

现在你可以选择删去树上的一条边，此时价值会变成断掉边之后形成的两棵树的价值和，你需要算出这个最大的价值和。

Input

第一行输入一行一个正整数$T[1\leq T\leq 10]$,代表数据的组数。

对于每组数据，第一行输入一个正整数$n[2\leq n\leq 10^5]$，代表树上的节点数。

第二行输入一行$n$个整数代表每个点的点权，保证点权范围在$[-10^9,10^9]$之间。

接下来$n-1$行，每行两个正整树$u,v[1\leq u,v\leq n]$代表边连接的两个点。

Output

对于每组数据，输出一行一个整数代表最大的价值。

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

19