Bob And The Magic Pairs
62% Success428 Attempts50 Points1s Time Limit256MB Memory1024 KB Max Code

Bob is a brilliant student in the class, so his teacher assigned him a problem. He has been given an array \(A\) containing \(N\) positive integers and two integers \(U\) and \(V\). He has been asked to find the number of magic pairs of array indices.

A pair of integers \((i, j)\) is called a magic pair if \(i < j\) and \(U ≤ A[i] \text{^} A[j] ≤ V\) where \(\text{^}\) denotes the bitwise XOR operation.

Help Bob to find the number of magic pairs in the given array.

Input Format:

  • The first line contains a single integer \(T\) denoting the number of test cases.
  • The first line of each test case contains the integers \(N\), \(U\), and \(V\) separated by spaces.
  • The second line of each test case contains \(N\) spaced integers, the elements of the array \(A\).

Output Format:

For each test case, print the number of magic pairs in the given array.

Constraints:

\(1 \leq T \leq 10\)
\(1 \leq N \leq 10^4\)
\(0 \leq A[i] \leq 10^9\)
\(0 \leq U \leq V \leq 10^9\)

Examples
Input
2
5 5 14
9 8 4 2 1
1 1 2
1
Output
8
0
Explanation

For test case 1:
There are 8 magic pairs in the given array:

  • A[0] XOR A[2] = 13
  • A[0] XOR A[3] = 11
  • A[0] XOR A[4] = 8
  • A[1] XOR A[2] = 12
  • A[1] XOR A[3] = 10
  • A[1] XOR A[4] = 9
  • A[2] XOR A[3] = 6
  • A[2] XOR A[4] = 5

For test case 2:
Since the array has only one element, there are no magic pairs.

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading Editor...
Results