Yarik 的生日即将到来,Mark 决定给他一个长度为 $$$n$$$ 的数组 $$$a$$$。
Mark 知道 Yarik 非常喜欢按位运算,而且他也有一个最喜欢的数字 $$$x$$$,所以 Mark 想找到最大的数字 $$$k$$$,这样就可以选择数字对 [$$$l_1, r_1$$$], [$$$l_2, r_2$$$], $$$\ldots$$$ [$$$l_k, r_k$$$],这样:
- $$$l_1 = 1$$$。
- $$$r_k = n$$$。
- $$$l_i \le r_i$$$ 适用于从 $$$1$$$ 到 $$$k$$$ 的所有 $$$i$$$。
- $$$r_i + 1 = l_{i + 1}$$$ 对于从 $$$1$$$ 到 $$$k - 1$$$ 的所有 $$$i$$$。
- $$$(a_{l_1} \oplus a_{l_1 + 1} \oplus \ldots \oplus a_{r_1}) | (a_{l_2} \oplus a_{l_2 + 1} \oplus \ldots \oplus a_{r_2}) | \ldots | (a_{l_k} \oplus a_{l_k + 1} \oplus \ldots \oplus a_{r_k}) \le x$$$,其中$$$\oplus$$$表示按位异或运算,$$$|$$$表示按位或运算。
如果这样的$$$k$$$不存在,则输出$$$-1$$$。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。以下行包含测试用例的描述。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$1 \le n \le 10^5, 0 \le x < 2^{30}$$$) - 分别是数组 $$$a$$$ 的长度和数字 $$$x$$$。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^{30}$$$) - 数组 $$$a$$$ 本身。
保证所有测试用例的 $$$n$$$ 值的总和不超过 $$$10^5$$$。
输出
对于每个测试用例,在单独的行上输出一个整数 - 最大合适数字 $$$k$$$,如果 $$$k$$$ 不存在,则输出 $$$-1$$$。
示例
输入 #1
8 3 1 1 2 3 2 2 1 1 2 2 1 3 2 3 0 0 3 2 0 0 1 4 2 1 3 3 7 2 2 2 3 5 0 0 1 2 2 1
输出 #1
2 2 1 2 3 -1 1 2
注意
在第一个测试用例中,您可以将 $$$k$$$ 等于 $$$2$$$ 并选择两个段 [$$$1, 1$$$] 和 [$$$2, 3$$$],$$$(1) | (2 \oplus 3) = 1$$$。可以证明 $$$2$$$ 是最大可能的答案。
在第二个测试用例中,段 [$$$1, 1$$$] 和 [$$$2, 2$$$] 是合适的,$$$(1) | (1) = 1$$$。不可能制作更多的段。
在第三个测试用例中,不可能选择 $$$2$$$ 段,如 $$$(1) | (3) = 3 > 2$$$,因此最佳答案是$$$1$$$。