Limits 2s, 1.0 GB

Sanvi is a very little and so much cute girl. She was playing with an array A of length N. While doing so, Sanvi discovers an interesting pattern with the pairing of two elements in that array. She defines a term ‘Happy Pair’ as pairing of two integer numbers, say P and Q, if bitwise XOR of these integers is a power of 2 i.e ( P XOR Q = 2^X ) , where X is an integer number. Now, she is challenging you with the following task.

You are an array A of length N having all positive integer numbers which are not greater than 20000. You have to answer Q queries in it. In each query, you are given four integers, say U, V, W and X representing indices of array A. You have to consider subarray from U to V (say A1) and subarray from W to X (say A2) and form pairing of values in one subarray with values in another one.

Your task is to find how many ways Happy Pairs can be chosen in between the values of these sub-arrays?

Input

Input starts with an integer T (1<=T<=5) denoting the total number of test cases. Each test case begins with an integer N (1 <= N <= 20000), denoting the length of array A. Next line contain N space separated integers denoting the values in array starting from 1 to N, which is nonnegative integer having value at most 20000.Next line will contain a single integer Q (1 <= Q <= 20000), denoting total number of quires. Following Q lines will contain four integers U, V, W and X ( U<=V and W<=X) separated by a single space between them.

Output

For every test cases, for each query, output an integer denoting total number of ways of forming Happy pairs in between the values of subarrays given in each query.

Sample

InputOutput
1
5
1 2 3 4 5
3
1 2 3 5
1 4 2 5
1 2 3 4
3
5
2

Submit

Login to submit.

Statistics

0% Solution Ratio
Toph uses cookies. By continuing you agree to our Cookie Policy.