311187: CF1946D. Birthday Gift

D. Birthday Gifttime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Yarik's birthday is coming soon, and Mark decided to give him an array $a$ of length $n$.

Mark knows that Yarik loves bitwise operations very much, and he also has a favorite number $x$, so Mark wants to find the maximum number $k$ such that it is possible to select pairs of numbers [$l_1, r_1$], [$l_2, r_2$], $\ldots$ [$l_k, r_k$], such that:

• $l_1 = 1$.
• $r_k = n$.
• $l_i \le r_i$ for all $i$ from $1$ to $k$.
• $r_i + 1 = l_{i + 1}$ for all $i$ from $1$ to $k - 1$.
• $(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$, where $\oplus$ denotes the operation of bitwise XOR, and $|$ denotes the operation of bitwise OR.

If such $k$ does not exist, then output $-1$.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The following lines contain the descriptions of the test cases.

The first line of each test case contains two integers $n$ and $x$ ($1 \le n \le 10^5, 0 \le x < 2^{30}$) — the length of the array $a$ and the number $x$ respectively.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i < 2^{30}$) — the array $a$ itself.

It is guaranteed that the sum of the values of $n$ across all test cases does not exceed $10^5$.

Output

For each test case, output a single integer on a separate line — the maximum suitable number $k$, and $-1$ if such $k$ does not exist.

ExampleInput

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

Output

2
2
1
2
3
-1
1
2

Note

In the first test case, you can take $k$ equal to $2$ and choose two segments [$1, 1$] and [$2, 3$], $(1) | (2 \oplus 3) = 1$. It can be shown that $2$ is the maximum possible answer.

In the second test case, the segments [$1, 1$] and [$2, 2$] are suitable, $(1) | (1) = 1$. It is not possible to make more segments.

In the third test case, it is not possible to choose $2$ segments, as $(1) | (3) = 3 > 2$, so the optimal answer is $1$.

题目大意：
Yarik的生日即将到来，Mark决定送给他一个长度为n的数组a。Yarik非常喜欢位运算，并且他有一个最喜欢的数字x，Mark想要找到最大的数k，使得可以选择数对[l1, r1], [l2, r2], ... [lk, rk]，满足以下条件：
- l1 = 1。
- rk = n。
- 对于所有1到k的i，li ≤ ri。
- 对于所有1到k-1的i，ri + 1 = li+1。
- (a[l1] ⊕ a[l1 + 1] ⊕ ... ⊕ a[r1]) | (a[l2] ⊕ a[l2 + 1] ⊕ ... ⊕ a[r2]) | ... | (a[lk] ⊕ a[lk + 1] ⊕ ... ⊕ a[rk]) ≤ x，其中⊕表示按位异或运算，|表示按位或运算。

如果这样的k不存在，则输出-1。

输入输出数据格式：
输入：
每个测试包含多个测试用例。第一行包含一个整数t（1 ≤ t ≤ 10^4）——测试用例的数量。接下来的行包含测试用例的描述。
每个测试用例的第一行包含两个整数n和x（1 ≤ n ≤ 10^5, 0 ≤ x < 2^30）——数组a的长度和数字x。
每个测试用例的第二行包含n个整数a1, a2, ..., an（0 ≤ ai < 2^30）——数组a本身。
保证所有测试用例中n的值的总和不超过10^5。

输出：
对于每个测试用例，输出一个单独的行——最大的合适数k，如果这样的k不存在，则输出-1。题目大意： Yarik的生日即将到来，Mark决定送给他一个长度为n的数组a。Yarik非常喜欢位运算，并且他有一个最喜欢的数字x，Mark想要找到最大的数k，使得可以选择数对[l1, r1], [l2, r2], ... [lk, rk]，满足以下条件： - l1 = 1。 - rk = n。 - 对于所有1到k的i，li ≤ ri。 - 对于所有1到k-1的i，ri + 1 = li+1。 - (a[l1] ⊕ a[l1 + 1] ⊕ ... ⊕ a[r1]) | (a[l2] ⊕ a[l2 + 1] ⊕ ... ⊕ a[r2]) | ... | (a[lk] ⊕ a[lk + 1] ⊕ ... ⊕ a[rk]) ≤ x，其中⊕表示按位异或运算，|表示按位或运算。 如果这样的k不存在，则输出-1。 输入输出数据格式： 输入： 每个测试包含多个测试用例。第一行包含一个整数t（1 ≤ t ≤ 10^4）——测试用例的数量。接下来的行包含测试用例的描述。 每个测试用例的第一行包含两个整数n和x（1 ≤ n ≤ 10^5, 0 ≤ x < 2^30）——数组a的长度和数字x。 每个测试用例的第二行包含n个整数a1, a2, ..., an（0 ≤ ai < 2^30）——数组a本身。 保证所有测试用例中n的值的总和不超过10^5。 输出： 对于每个测试用例，输出一个单独的行——最大的合适数k，如果这样的k不存在，则输出-1。