Sorting Algorithm

Limits 2s, 512 MB

Given an array $A$ with $N$ elements that is sorted in 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 (in non-decreasing order):

For each $i$ such that $L\leq i\leq 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~(1\leq T\leq 10^5)$ , denoting the number of test cases.

Each case starts with an integer $N~(1\leq N\leq 10^5)$ , denoting the number of elements in the array $A$ . The next line will contain $N$ integers separated by spaces which denote the elements of the array $(1\leq A_i<2^{20})$ . It is guaranteed that the array is sorted, that is, $A_i\leq A_{i+1}$ for all $1\leq i < N$ .

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

It is further guaranteed that the sum of $N$ over all test cases will not exceed $10^5$ , and that the sum of $Q$ over all test cases will not exceed $10^5$ .

Output

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

Sample

Input	Output
1 4 1 4 5 5 3 1 2 2 3 1 4	2 2 262144
In the first query there are two values for $X$ : $0, 1$ . For $X = 0$ , the array becomes $A = [1, 4, 5, 5]$ if the operation is performed. For $X = 1$ , the array becomes $A = [0, 5, 5, 5]$ if the operation is performed. In the second query there are two values for $X$ : $0, 6$ . For $X = 0$ , the array becomes $A = [1, 4, 5, 5]$ if the operation is performed. For $X = 6$ , the array becomes $A = [1, 2, 3, 5]$ if the operation is performed. Bitwise XOR. The bitwise XOR of non-negative integers $A$ and $B$ , denoted $A\oplus B$ , is defined as follows: When $A\oplus B$ is written in base two, the $k$ -th digit from the right $(k\geq 0)$ is $1$ if and only if exactly one of the digits in that place of $A$ and $B$ is $1$ , and $0$ otherwise. For example, we have $3\oplus 5=6$ (in base two: $011\oplus 101=110$ ).

Input

Output

2
2
262144

In the first query there are two values for $X$ : $0, 1$ .

For $X = 0$ , the array becomes $A = [1, 4, 5, 5]$ if the operation is performed.
For $X = 1$ , the array becomes $A = [0, 5, 5, 5]$ if the operation is performed.

In the second query there are two values for $X$ : $0, 6$ .

For $X = 0$ , the array becomes $A = [1, 4, 5, 5]$ if the operation is performed.
For $X = 6$ , the array becomes $A = [1, 2, 3, 5]$ if the operation is performed.

Bitwise XOR. The bitwise XOR of non-negative integers $A$ and $B$ , denoted $A\oplus B$ , is defined as follows:

When $A\oplus B$ is written in base two, the $k$ -th digit from the right $(k\geq 0)$ is $1$ if and only if exactly one of the digits in that place of $A$ and $B$ is $1$ , and $0$ otherwise.

For example, we have $3\oplus 5=6$ (in base two: $011\oplus 101=110$ ).