Interesting Numbers

The bitwise exclusive or, or simply XOR, is an operation denoted by $\oplus$ that works on two integers by XOR-ing their corresponding bits. If $x_i, y_i, z_i$ denote the $i$-th binary digit of $x$, $y$, and $z$, where $z = x \oplus y$, then $z_i = (x_i + y_i) \mod 2$.

You are given a positive integer $k$. A sequence of integers is interesting if the XOR of any two of its elements is less than or equal to $k$.

Given a sequence $a_1, \dots, a_n$, determine the largest possible length of an interesting subsequence. A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements.

The first line contains the number of test cases $z$ ($1 \leq z \leq 1\,000$). The descriptions of the test cases follow.

The first line of each case contains two integers $n$ and $k$ ($1 \leq n \leq 30\,000$, $1 \leq k < 2^{20}$), the length of the sequence and the upper bound on the maximum XOR of its two elements.

The second line contains $n$ nonnegative integers $a_1, \dots, a_n$ ($0 \leq a_i < 2^{20}$), the given sequence.

The sum of $n$ over all test cases does not exceed $200\,000$, and the sum of $k$ over all test cases does not exceed $3\,200\,000$.

For every test case, output a single integer, the maximum possible length of an interesting subsequence of the given sequence.

The elements 3, 9, 10, and 3 form an interesting subsequence, since the XOR of every pair is at most 11. For example, $9 \oplus 10 = 1001_2 \oplus 1010_2 = 11_2 = 3 \leq 11$. No subsequence of five elements has this property. For example, $(3, 9, 10, 3, 4)$ is not interesting because $4 \oplus 9 = 100_2 \oplus 1001_2 = 1101_2 = 13 > 11$.