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\)