You are given a tree rooted at $1$ with $n$ vertices and a permutation $p$ of length $n$ consisting of integers $0, 1, \ldots, n - 1$, where $p_v$ represents the weight of vertex $v$.

Let $S_v$ denote the set of weights written on the vertices belonging to the path from $1$ to $v$. Define a function $f$ as $f(v) = \mathrm{MEX}(S_v)$, that is, the $\mathrm{MEX}$ over the set consisting of the weights of vertices on the simple path between the root and $v$ (inclusive), where $\operatorname{MEX}$ of a collection of integers $c_1, c_2, \ldots, c_k$ is defined as the smallest non-negative integer $x$ which does not occur in the collection $c$.

Also, given the following operation:

• Choose an integer $v$ ($1 \leq v \leq n$) and assign $f(v)$ to $p_v$.

Your goal is to find the maximum value of $\sum\limits_{v = 1}^n f(v)$ after performing the above operation no more than once (possibly zero).

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 2 \cdot 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of vertices of the tree.

The second line of each test case contains $n$ integers $p_1, p_2, \ldots, p_n$ ($0 \le p_i \le n - 1$) — the elements of array $p$. It is guaranteed that every integer from $0$ to $n - 1$ appears exactly once in $p$.

Then $n - 1$ lines follow, each line contains two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$), indicating an edge between vertices $x_i$ and $y_i$. It is guaranteed that these edges form a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single line containing an integer: the maximum value of $\sum\limits_{v = 1}^n f(v)$ after performing the above operation no more than once (possibly zero).

Note

In the first example, not doing any operation is optimal, so the answer is $1$.

In the second example, we have

• $f(1) = \mathrm{MEX}(\{p_1\}) = \mathrm{MEX}(\{1\}) = 0$
• $f(2) = \mathrm{MEX}(\{p_1, p_2\}) = \mathrm{MEX}(\{1, 0\}) = 2$
• $f(3) = \mathrm{MEX}(\{p_1, p_3\}) = \mathrm{MEX}(\{1, 2\}) = 0$

And we have the following options:

1. Doing nothing would lead to $\sum\limits_{v = 1}^n f(v) = 2$
2. Doing operation on vertex $1$ would assign $f(1) = 0$ to $p_1$, change $f(1), f(2), f(3)$ to $1$, which leads to $\sum\limits_{v = 1}^n f(v) = 3$
3. Doing operation on vertex $2$ would assign $f(2) = 2$ to $p_2$, change $f(2)$ to $0$, which leads to $\sum\limits_{v = 1}^n f(v) = 0$
4. Doing operation on vertex $3$ would assign $f(3) = 0$ to $p_3$, change $f(3)$ to $2$, which leads to $\sum\limits_{v = 1}^n f(v) = 4$

So the answer is $4$, by doing operation on vertex $3$.