Chiaki 有一棵包含 $n$ 个节点的树，节点编号为 $1$ 到 $n$。每个节点上都有一个正整数权值 $w_i$。

Chiaki 想知道有多少个无序点对 $(u, v)$ 满足： 设 $t_1 \to t_2 \to \dots \to t_k$ ($t_1 = u, t_k = v$) 为从 $u$ 到 $v$ 的最短路径。那么序列 $w_{t_1}, w_{t_2}, \dots, w_{t_k}$ 或者序列 $w_{t_k}, w_{t_{k-1}}, \dots, w_{t_1}$ 可以通过若干次循环移位操作变为非递减序列。

注意，循环移位操作是指将序列中的元素进行重排，即将最后一个元素移动到第一个位置，同时将其他所有元素向后移动一位，或者执行该操作的逆操作。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。 对于每组测试数据： 第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示树的节点数。 第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 10^5$)。 接下来的 $n - 1$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n, u \neq v$)，表示树的一条边。 保证所有测试数据中 $n$ 的总和不超过 $10^5$。

输出格式

对于每组测试数据，输出一个整数表示答案。

样例

样例输入 1

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

样例输出 1

10