E. Спаси меня!
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
16 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Обратите внимание на необычное ограничение по памяти.

Помогите, я оказался в ловушке магической печати!

Есть массив $$$a$$$ из $$$n$$$ целых чисел. За одну операцию можно выбрать $$$1\le i\le n - 1$$$ и либо:

  • Присвоить $$$a_i := a_i \oplus a_{i+1}$$$$$$^{\text{∗}}$$$.
  • Присвоить $$$a_{i+1} := a_i \oplus a_{i+1}$$$.

Печать считается разрушенной, как только появится индекс $$$i$$$ такой, что $$$a_i = 0$$$. Определите минимальное количество операций, необходимое для разрушения печати, или выведите $$$-1$$$, если выбраться невозможно!

$$$^{\text{∗}}$$$$$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных дано одно целое число $$$n$$$ ($$$1\le n\le 100$$$) — количество элементов в массиве.

Во второй строке даны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \lt 2^{25}$$$) — элементы массива $$$a$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$100$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число: минимальное количество операций, необходимое для разрушения печати, или $$$-1$$$, если это невозможно.

Пример
Входные данные
5
3
1 2 1
4
4 2 3 1
5
1 2 4 8 16
3
0 1 2
1
1234
Выходные данные
3
2
-1
0
-1
Примечание

В первом примере можно выполнить следующую последовательность операций:

  1. Присвоить $$$a_1 := a_1 \oplus a_2 = 3$$$: новый массив — $$$[3, 2, 1]$$$.
  2. Присвоить $$$a_2 := a_1 \oplus a_2 = 1$$$: новый массив — $$$[3, 1, 1]$$$.
  3. Присвоить $$$a_3 := a_2 \oplus a_3 = 0$$$: новый массив — $$$[3, 1, 0]$$$, и печать разрушена.

В третьем примере можно доказать, что ни одна последовательность операций не разрушает печать.