Birthday Gift
Contest: Codeforces Round 936 (Div. 2)
Difficulty rating: 1900
Tags: bitmasks, brute force, constructive algorithms, greedy, implementation

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 format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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$$$.

Example input:
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

Example output:
2
2
1
2
3
-1
1
2

Editorial:
For convenience, let's increase $$$x$$$ by $$$1$$$, and then iterate through the bit in which the final number is less than $$$x$$$. We will iterate from the most significant bit to the least significant bit, denoting it as $$$i$$$. The initial bit will be $$$30$$$. Let's look at all the numbers $$$a$$$ in which this bit is $$$1$$$.
If there is an odd number of such numbers, then the $$$\oplus$$$ of some subsegment will be odd, and therefore the final $$$|$$$ will also be odd. If at the same time the bit $$$i$$$ in $$$x$$$ is $$$0$$$, then the process needs to be terminated, because in all the other bits it will no longer be possible to decrease the final number. If, however, in $$$x$$$ this bit is also $$$1$$$, then we need to move on to the less significant bits, since in both numbers this bit will always be $$$1$$$.
If the number of numbers with $$$1$$$ in bit $$$i$$$ is even, then in order to make this bit $$$0$$$ in the final number, each segment must contain an even number of such numbers, and since we want to maximize the number of segments, each segment must contain exactly $$$2$$$ such numbers. For this, for every two indices $$$l$$$ and $$$r$$$, such that $$$a_{l}$$$ and $$$a_{r}$$$ in bit $$$i$$$ contain $$$1$$$, and all numbers from $$$a_{l + 1}$$$ to $$$a_{r - 1}$$$ contain $$$0$$$, replace the subsegment $$$[l, r]$$$ with $$$a_{l} \oplus a_{l + 1} \oplus \ldots \oplus a_{r}$$$. After this, if there is a $$$1$$$ in $$$x$$$ in this bit, update the answer and return the array to its original state. Then move on to the less significant bits.
There is also an alternative solution that also iterates through the bits from the most significant to the least significant, but instead of compressing subsegments into one number, it uses a greedy algorithm.