You are given a tree of $N$ nodes rooted at node $1$ and each node has a value where value of $i'th$ node is $A_i$.
You're given $Q$ queries, in each query two integers $x, k$ given. Find if possible such that all nodes in the subtree of node $x$ (including $x$) has values greater than or equal to $k$ by performing swapping of two nodes any number of times. You can swap two nodes $u$ and $v$ such that $u$ belongs to subtree of $x$ (including $x$) and $v$ does not. If possible then find minimum number of swapping of nodes required otherwise print $-1$.
Note: Since the queries are independent, the initial tree is retained after each query.

  Input format

• The first line contains $T$ denoting the number of test cases. The description of each test case is as follows.
  • The first line contains an integer $N$ denoting the number of nodes in tree.
  • Next line contains space-separated integers denoting value of each node.
  • Each of the following $N - 1$ lines contain two integers $u$ and $v$ denoting edge between nodes $u$ and $v$.
  • The next line contains a single integer $Q$ - the number of queries.
  • Next $Q$ lines contain two space-separated integers $x, k$.

Output format

For query print the answer in a new line.

Constraints

$1 \leq T \leq 10$

$2 \leq N \leq 2 * 10^5$

$1 \leq A_i, k \leq 10^6$

$1 \leq u, v \leq N$

$1 \leq Q \leq 10^5$

$2 \leq x \leq N$