D. XOR Pairing
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
Excess is just as bad as deficiency.
— Confucius, The Analects

OP, a senior high school student, had fallen in love with the bitwise XOR operation.

So is there anything that can be done for OP? Don't worry, CY has a wonderful idea.

CY gives OP an array $$$a$$$ consisting of exactly $$$n$$$ numbers and a non-negative integer $$$k$$$. And then, CY throws him a question:

How many pairs $$$(i,j)$$$ $$$(1 \leq i \lt j \leq n)$$$ satisfy $$$a_i \oplus a_j = k$$$? Here $$$\oplus$$$ denotes the bitwise XOR operation$$$^{\dagger}$$$.

$$$^{\dagger}$$$ Bitwise XOR operation is a binary operation that takes two bit patterns of equal length and performs the logical exclusive OR operation on each pair of corresponding bits. The result in each position is $$$\mathtt{1}$$$ if only one of the bits is $$$\mathtt{1}$$$, but will be $$$\mathtt{0}$$$ if both are $$$\mathtt{0}$$$ or both are $$$\mathtt{1}$$$. In this, we perform the comparison of two bits, being $$$\mathtt{1}$$$ if the two bits are different, and $$$\mathtt{0}$$$ if they are the same. For example:

    0101 (decimal 5)
XOR 0011 (decimal 3)
  = 0110 (decimal 6)
Input

The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10 ^ 4)$$$, denoting the number of test cases.

The first line of each test case contains two integers $$$n$$$, $$$k$$$ $$$(1 \leq n \leq 2 \times 10 ^ 5, 0 \leq k \leq 10 ^ 9)$$$.

The second line contains exactly $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(0 \leq a_i \leq 10 ^ 9)$$$.

It's guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \times 10 ^ 5$$$.

Output

For each test case, output a single integer, denoting the number of pairs $$$(i, j)$$$ satisfying $$$a_i \oplus a_j = k$$$.

Example
Input
2
6 1
1 1 4 5 1 4
7 0
1 9 1 9 8 1 0
Output
2
4
Note

In the first test case, only two pairs $$$(3, 4)$$$, $$$(4, 6)$$$ satisfy the constraint: $$$a_3 \oplus a_4=a_4 \oplus a_6 = 1$$$.

In the second test case, there are four pairs $$$(1, 3)$$$, $$$(1, 6)$$$, $$$(2, 4)$$$, $$$(3, 6)$$$ satisfy the constraint: $$$a_1 \oplus a_3=a_1 \oplus a_6 = a_2 \oplus a_4 = a_3 \oplus a_6 = 0$$$.