You are given an array A of n integers (1 based indexing). From any index $i$ of this array we can move to the following indexes:

• any index $j$ such that the value of $k = abs(i-j)$  has only one bit set in its binary form. For example: $k$ can be $1 \rightarrow (1)_2$ $2 \rightarrow (10)_2$, $4 \rightarrow (100)_2$ , $8 \rightarrow (1000)_2$
• iff (if and only if) --> $(n−i) \% 2 = 0$ so we can move to index $j$ such that it value is $(n + i) / 2$
• iff (if and only if) --> $i \%2 = 1$ so we can move to index $j$ such that its value is$(i + 1) / 2$

Now You have to answer Q queries, in each query, you are given a start index A and an end index B, you have to find the minimum number of attempts to reach from starting index A to the ending index B.

INPUT:

• The first line of each test case contains a single integer $n$  denoting the size of the array.
• Next line contains $n$ space-separated integers denoting elements of the array.
• Next line contains a single integer $Q$ , denoting the number of queries.
• Next Q lines contain two space-separated integers A and B.

OUTPUT:

• For each query you have to find the minimum number of attempts to reach from starting index A to the ending index B.

CONSTRAINTS:

$1≤N≤1000$

$1≤Q≤10^6$

$1≤Ai≤10^9$

$1<=A,B<=n$