I. 有趣的数（Interesting Numbers）

题目描述

按位异或（XOR）是一种二进制运算，通常记作 xor 或 $\oplus$。

对于两个整数 $x$ 和 $y$，令：

$$z = x \oplus y$$

如果 $x_i, y_i, z_i$ 分别表示 $x, y, z$ 的第 $i$ 位二进制位，那么：

$$z_i = (x_i + y_i) \bmod 2$$

也就是说：

• 当两个二进制位不同的时候，该位异或结果为 $1$；
• 当两个二进制位相同的时候，该位异或结果为 $0$。

现在给定一个正整数 $k$。

如果一个整数序列中，任意两个元素的异或值都不超过 $k$，即对于序列中任意两个元素 $u, v$ 都满足：

$$u \oplus v \le k$$

那么称这个序列是有趣的。

给定一个长度为 $n$ 的序列：

$$a_1, a_2, \ldots, a_n$$

请你求出它的一个有趣子序列的最大可能长度。

这里的子序列指：从原序列中删除若干个元素，也可以一个都不删，并保持剩余元素的相对顺序后得到的序列。

注意：本题只要求输出最大长度，不要求输出具体子序列。

---

输入格式

第一行包含一个整数 $z$，表示测试用例组数。

接下来依次给出 $z$ 组测试用例。

每组测试用例包含两行。

第一行包含两个整数 $n$ 和 $k$，分别表示序列长度，以及任意两数异或值允许的最大上界。

第二行包含 $n$ 个非负整数：

$$a_1, a_2, \ldots, a_n$$

表示给定序列。

---

输出格式

对于每组测试用例，输出一行一个整数，表示该测试用例中有趣子序列的最大长度。

---

数据范围

对于所有测试数据：

$$1 \le z \le 1000$$

对于每组测试用例：

$$1 \le n \le 30000$$ $$1 \le k < 2^{20}$$ $$0 \le a_i < 2^{20}$$

并且所有测试用例满足：

$$\sum n \le 200000$$ $$\sum k \le 3200000$$

---

样例输入

1
7 11
3 12 9 10 16 3 4

样例输出

4

---

样例解释

可以选择子序列：

$$3,\ 9,\ 10,\ 3$$

这个子序列是有趣的，因为其中任意两个数的异或值都不超过 $11$。

例如：

$$9 \oplus 10 = 1001_2 \oplus 1010_2 = 0011_2 = 3 \le 11$$

又例如：

$$3 \oplus 9 = 0011_2 \oplus 1001_2 = 1010_2 = 10 \le 11$$

因此答案至少为 $4$。

但是不存在长度为 $5$ 的有趣子序列。比如如果尝试选择：

$$3,\ 9,\ 10,\ 3,\ 4$$

则有：

$$4 \oplus 9 = 0100_2 \oplus 1001_2 = 1101_2 = 13 > 11$$

所以它不是有趣子序列。

因此最大长度为：

$$4$$