A1. Бурёнка и традиции (простая версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это упрощенная версия этой задачи. Разница между легкой и сложной версиями заключается в ограничениях на $$$a_i$$$ и на $$$n$$$. Вы можете делать взломы только в том случае, если обе версии задачи решены.

Бурёнка — наследная принцесса Бурятии, и скоро она станет $$$n$$$-й по счёту королевой страны. В Бурятии есть древняя традиция — правитель перед своей коронацией должен показать жителям свою силу. Чтобы определить силу $$$n$$$-го правителя, жители страны дают ему массив $$$a$$$ из ровно $$$n$$$ чисел, после чего он должен превратить все элементы массива в нули за наименьшее время. Правитель может любое число раз выполнить следующую операцию из двух шагов:

  • выбрать два индекса $$$l$$$ и $$$r$$$ такие, что $$$1 \le l \le r \le n$$$ и целое неотрицательное число $$$x$$$, затем
  • для всех $$$l \leq i \leq r$$$ присвоить $$$a_i := a_i \oplus x$$$, где $$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ. На эту операцию он потратит $$$\left\lceil \frac{r-l+1}{2} \right\rceil$$$ секунд, где $$$\lceil y \rceil$$$ обозначает округление числа $$$y$$$ вверх до ближайшего целого.

Помогите Буренке посчитать, сколько времени ей понадобится.

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

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

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

Во второй строке каждого набора входных данных содержатся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 5000$$$) — элементы массива.

Сумма $$$n$$$ по всем тестам не превосходит $$$5000$$$.

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

Для каждого набора входных данных выведите единственное число — минимальное время, которое понадобится Буренке.

Пример
Входные данные
7
4
5 5 5 5
3
1 3 2
2
0 0
3
2 5 7
6
1 2 3 3 2 1
10
27 27 34 32 2 31 23 56 52 4
5
1822 1799 57 23 55
Выходные данные
2
2
0
2
4
7
4
Примечание

В первом наборе входных данных Бурёнка может выбрать индексы $$$l = 1$$$, $$$r = 4$$$ и $$$x=5$$$. так он заполнит массив нулями за $$$2$$$ секунды.

Во втором наборе входных данных Бурёнка сначала выбирает индексы $$$l = 1$$$, $$$r = 2$$$ и $$$x = 1$$$, после чего $$$a = [0, 2, 2]$$$, а затем индексы $$$l = 2$$$, $$$r = 3$$$ и $$$x=2$$$, что заполняет массив нулями. Суммарно Бурёнка потратит $$$2$$$ секунды.