A. Единичный массив
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан массив $$$a$$$ длины $$$n$$$, элементы которого равны $$$-1$$$ и $$$1$$$. Назовём массив $$$a$$$ хорошим, если одновременно выполняются следующие условия:

  • $$$a_1 + a_2 + \ldots + a_n \ge 0$$$;

  • $$$a_1 \cdot a_2 \cdot \ldots \cdot a_n = 1$$$.

За одну операцию вы можете выбрать произвольный элемент массива $$$a_i$$$ и изменить его значение на противоположное. Другими словами, если $$$a_i = -1$$$, то вы можете присвоить значение $$$a_i := 1$$$, а если $$$a_i = 1$$$, то присвоить значение $$$a_i := -1$$$.

Определите минимальное количество операций, которые нужно сделать, чтобы массив $$$a$$$ стал хорошим. Можно показать, что это всегда возможно.

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

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

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

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

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

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

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

В первом наборе входных данных мы можем присвоить значение $$$a_1 := 1$$$. Тогда $$$a_1 + a_2 + a_3 + a_4 = 1 + (-1) + 1 + (-1) = 0 \ge 0$$$ и $$$a_1 \cdot a_2 \cdot a_3 \cdot a_4 = 1 \cdot (-1) \cdot 1 \cdot (-1) = 1$$$. Таким образом, мы сделали $$$1$$$ операцию.

Во втором наборе входных данных мы можем присвоить $$$a_1 := 1$$$. Тогда $$$a_1 + a_2 + a_3 + a_4 + a_5 = 1 + (-1) + (-1) + 1 + 1 = 1 \ge 0$$$ и $$$a_1 \cdot a_2 \cdot a_3 \cdot a_4 \cdot a_5 = 1 \cdot (-1) \cdot (-1) \cdot 1 \cdot 1 = 1$$$. Таким образом, мы сделали $$$1$$$ операцию.

В третьем наборе входных данных $$$a_1 + a_2 + a_3 + a_4 = (-1) + 1 + (-1) + 1 = 0 \ge 0$$$ и $$$a_1 \cdot a_2 \cdot a_3 \cdot a_4 = (-1) \cdot 1 \cdot (-1) \cdot 1 = 1$$$. Таким образом, все условия уже выполнены и можно не делать операции.

В четвёртом наборе входных данных мы можем присвоить значения $$$a_1 := 1, a_2 := 1, a_3 := 1$$$. Тогда $$$a_1 + a_2 + a_3 = 1 + 1 + 1 = 3 \ge 0$$$ и $$$a_1 \cdot a_2 \cdot a_3 = 1 \cdot 1 \cdot 1 = 1$$$. Таким образом, мы сделали $$$3$$$ операции.