XORted
Description
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 < 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 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
For each query, you have to print a line containing the number of such $X$.
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$.
1
4
1 4 5 5
3
1 2
2 3
1 4
2
2
262144