给定一棵包含 $n$ 个节点和 $n-1$ 条边的树，所有节点连通。每个节点 $i$ 都有一个权值 $a_i$。一只猴子在树上跳跃。在每次跳跃中，它可以沿着边从一个节点移动到另一个节点。如果猴子从节点 $u_1$ 出发，经过 $u_2, u_3, \dots, u_{k-1}$，最后到达 $u_k$，且所有经过的节点互不相同，我们称 $u_1, u_2, u_3, \dots, u_k$ 为一条简单路径。我们定义简单路径 $u_1, u_2, u_3, \dots, u_k$ 的 LIS（最长上升子序列）如下：

• 满足 $1 = p_1 < p_2 < \dots < p_l \le k$ 且 $a_{u_{p_1}} < a_{u_{p_2}} < \dots < a_{u_{p_l}}$ 的最长序列 $p_1, p_2, \dots, p_l$。

猴子希望使 LIS 尽可能长。对于每个 $i \in [1, n]$，请计算如果它从节点 $i$ 出发，能够获得的最长 LIS 的长度。

输入格式

输入的第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^5$)，表示节点数。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)，表示每个节点的权值。 接下来的 $n-1$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n$)，表示连接节点 $u$ 和 $v$ 的边。保证给定的边构成一棵树。 保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

输出格式

对于每个测试用例，输出 $n$ 行，第 $i$ 行表示从节点 $i$ 出发时猴子能获得的最长 LIS 的长度。

样例

输入 1

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

输出 1

3
2
2
2
1
2
2
1
2
3