You are given an undirected tree with $N$ nodes rooted at node 1. Every node has a value $A[i]$ assigned to it. You are required to answer $Q$ queries of the following type:

• $V X$: Find the longest length prefix that is common in the binary representation of $V$ and the binary representation of node value of any of the ancestors of node $X$ including node $X$ itself. Also, the binary representation should be of length $62$ and of the order from Most Significant Bit to Least Significant Bit.

Find the required answer for $Q$ queries.

Note:

• Assume 1-based indexing.
• A node $u$ is said to be an ancestor of node $v$, if node $u$ lies on a simple path between the root and node $v$.
• The prefix of a binary representation is defined as a contiguous set of bits from the starting of the representation. 

Input format

• The first line contains a single integer $T$ that denotes the number of test cases.
• For each test case:
  • The first line contains an integer $N$.
  • The second line contains $N$ space-separated integers denoting array $A$.
  • Next $N - 1$ lines contain two space-separated integers $u v$ denoting an edge between node $u$ and $v$.
  • The next line contains an integer $Q$.
  • Next $Q$ lines contain two space-separated integers $V X$ denoting the query.

Output format

For each test case, print $Q$ space-separated integers denoting the longest length common prefix for $Q$ queries. Print the output for each test case in a new line.

Constraints

$1 \le T \le 5 \\ 1 \le N, Q \le 10^5 \\ 1 \le A[i], V \le 10^9 \\ 1 \le X \le N$