A number M is said to be a Mystical Number with respect to a number X if $(M \oplus X) > (M$ \& X).

You are given an array A of size N. You are also given Q queries. Each query consists of three integers L, R, and X.

For each query, find the count of Mystical Numbers in the subarray A[L:R] with respect to the number X.

Notes:
$\oplus$ represents the [Bitwise XOR] operation and \& represents the [Bitwise AND] operation.
A[L:R] denotes the subarray $A[L], A[L+1], \ldots, A[R]$.

------ Input Format ------

• The first line contains a single integer T - the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer N - the size of the array A.
• The second line of each test case contains $N space-separated integers A_{1}, A_{2}, \dots, A_{N}$ denoting the array A.
• The third line of each test case contains an integer Q - denoting the number of queries.
• The i^{th} of the next Q lines contains three space-separated integers L , R and X.

------ Output Format ------

For each testcase,
- For each query, print in a new line, the count of *Mystical $Numbers* among A[L], A[L+1], \ldots, A[R]$ with respect to the number X.

------ Constraints ------

$1 ≤ T ≤ 100$
$1 ≤ N ≤ 2 \cdot 10^{5}$
$0 ≤ A_{i} < 2^{31}$
$1 ≤ Q ≤ 2 \cdot 10^{5}$
$1 ≤ L ≤ R ≤ N$
$0 ≤ X < 2^{31}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$.
- Sum of $Q$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------
1
5
1 2 3 4 5
2
1 5 4
2 5 2
----- Sample Output 1 ------
3
2
----- explanation 1 ------
Test case $1$:
- Query $1$: $L = 1 , R = 5 , X = 4$.
- $A_{1} \oplus X = 5, A_{1} \& X = 0$.
- $A_{2} \oplus X = 6, A_{2} \& X = 0$.
- $A_{3} \oplus X = 7, A_{3} \& X = 0$.
- $A_{4} \oplus X = 0, A_{4} \& X = 4$.
- $A_{5} \oplus X = 1, A_{5} \& X = 4$.

Mystical numbers are $A_{1} , A_{2},$ and $A_{3}$ with respect to $4$. Therefore, the answer to this query is $3$.
- Query $2$: $L = 2 , R = 5 , X = 2$.
- $A_{2} \oplus X = 0, A_{2} \& X = 2$.
- $A_{3} \oplus X = 1, A_{3} \& X = 2$.
- $A_{4} \oplus X = 6, A_{4} \& X = 0$.
- $A_{5} \oplus X = 7, A_{5} \& X = 0$.

Mystical numbers are $A_{4}$ and $A_{5}$ with respect to $2$. Therefore , the answer to this query is $2$.

见题面

见题面