Zayin 给你一棵有 $n$ 个节点的树（节点编号从 $1$ 到 $n$）。每个节点 $i$ 都有一个权值 $a_i$。

你可以选择树上的一条简单路径。设 $P$ 为路径上的节点数，$R$ 为路径上权值的最大值，$L$ 为路径上权值的最小值。

请选择一条路径，使得 $P - R + L$ 最小。输出 $P - R + L$ 的最小值。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$，表示节点数。

下一行包含 $n$ 个整数，第 $i$ 个整数为 $a_i$ ($0 \le a_i \le 10^6$)。

接下来的 $n-1$ 行描述树的边。每行包含两个整数 $u_i$ 和 $v_i$，表示节点 $u_i$ 和 $v_i$ 之间有一条边。

所有测试用例中 $n$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，输出 $P - R + L$ 的最小值。

样例

样例输入 1

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

样例输出 1

0
-1

说明

在第一个样例中，你可以选择路径 $(2,5)$。

在第二个样例中，你可以选择路径 $(2,3)$。