J. XORted
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a sorted array $$$A$$$ with $$$N$$$ elements (non-decreasing order), you will be given $$$Q$$$ queries. In each query, you will be given a range $$$[L, R]$$$. For each query, you have to find the number of non-negative integers $$$X$$$ such that $$$X \lt 2^{20}$$$ and after doing the following operation the whole array remains sorted (non-decreasing order):

  • For each $$$i$$$ such that $$$L \le i \le R$$$, assign $$$A_i := A_i \oplus X$$$.

Note that the queries are independent. So you do not actually apply the operations on the array when you move on to the next query.

Input

Input starts with an integer $$$T\space(1 \le T \le 10^5)$$$, denoting the number of test cases.

Each case starts with an integer $$$N\space(1 \le N \le 10^5)$$$, denoting the number of elements in the array $$$A$$$. The next line will contain $$$N$$$ integers $$$A_1,A_2, ...., A_N\space(1 \le A_i \lt 2^{20})$$$ separated by spaces which denote the elements of the array.

The next line contains an integer $$$Q\space(1 \le Q \le 10^5)$$$ which denotes the number of queries. Each of the next $$$Q$$$ lines contains two space separated integer denoting $$$L$$$ and $$$R\space(1 \le L \le R \le N)$$$.

Additional constraint on the input:

  • $$$\sum N \le 10^5$$$ over all test cases
  • $$$\sum Q \le 10^5$$$ over all test cases
Output

For each query, you have to print a line containing the number of such $$$X$$$.

Example
Input
1
4
1 4 5 5
3
1 2
2 3
1 4
Output
2
2
262144