D. Подарок на день рождения
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Совсем скоро у Ярика день рождения, и Марк решил подарить ему массив $$$a$$$ длины $$$n$$$.

Марк знает, что Ярик очень любит битовые операции, а также у него есть любимое число $$$x$$$, поэтому Марк хочет найти такое максимальное число $$$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$$$ для всех $$$i$$$ от $$$1$$$ до $$$k$$$.
  • $$$r_i + 1 = l_{i + 1}$$$ для всех $$$i$$$ от $$$1$$$ до $$$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$$$, где $$$\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$$$, и $$$-1$$$, если такого $$$k$$$ не существует.

Пример
Входные данные
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
Выходные данные
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$$$.