You are given an array of $N$ positive integers and $Q$ queries. In each query, you are given two integers $l$ and $r$.

For each query, find the length of the longest subarray such that the bitwise $AND$ of the subarray is $2^k$ where $l \leq k \leq r$ and if no subarray exists, then the answer will be $0$.

 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 array elements.
  • The next line contains $N$ space-separated integers.
  • The next line contains an integer $Q$ denoting the number of queries that are required to be performed.
  • Each of the next $Q$ lines contains two integers $l$ and $r$.

Output format

For each test case, $Q$ lines must be printed and the $i^{th}$ line should contain the output for the $i^{th}$ query.

Constraints

$1 \leq T \leq 20$

$1 \leq N, Q \leq 5 * 10^5$

$1 \leq A_i \leq 10^{18}$

$0 \leq l \leq r \leq 60$