按位异或（bitwise exclusive or），简称 XOR，是一种用 $\oplus$ 表示的运算，它通过对两个整数的对应二进制位进行异或来工作：如果 $x_i, y_i, z_i$ 分别表示 $x, y$ 和 $z$ 的第 $i$ 个二进制位，其中 $z = x \oplus y$，则 $z_i = (x_i + y_i) \pmod 2$。

给定一个正整数 $k$。如果一个整数序列中任意两个元素的异或值都小于或等于 $k$，则称该序列为“有趣的”。

给定一个序列 $a_1, \dots, a_n$，确定其有趣的子序列的最大可能长度。（子序列是指可以通过从给定序列中删除零个或多个元素而得到的序列。）

输入格式

输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 1000$)。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n, k$ ($1 \le n \le 30\,000, 1 \le k < 2^{20}$)，分别表示序列的长度和任意两个元素异或值的上限。

第二行包含 $n$ 个非负整数 $a_1, \dots, a_n$ ($0 \le a_i < 2^{20}$)，即上述给定的序列。

所有测试用例中 $n$ 的总和不超过 $200\,000$，$k$ 的总和不超过 $3\,200\,000$。

输出格式

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

样例

样例输入 1

1
7 11
3 12 9 10 16 3 4

样例输出 1

4

说明

元素 $3, 9, 10$ 和 $3$ 构成了一个有趣的子序列，因为其中任意一对元素的异或值都不大于 $11$。例如 $9 \oplus 10 = 1001_2 \oplus 1010_2 = 11_2 = 3 \le 11$。不存在由五个元素组成的满足该性质的子序列，例如序列 $(3, 9, 10, 3, 4)$ 就不是有趣的，因为 $4 \oplus 9 = 100_2 \oplus 1001_2 = 1101_2 = 13 > 11$。