310441: CF1834A. Unit Array

A. Unit Arraytime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Given an array $a$ of length $n$, which elements are equal to $-1$ and $1$. Let's call the array $a$ good if the following conditions are held at the same time:

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

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

In one operation, you can select an arbitrary element of the array $a_i$ and change its value to the opposite. In other words, if $a_i = -1$, you can assign the value to $a_i := 1$, and if $a_i = 1$, then assign the value to $a_i := -1$.

Determine the minimum number of operations you need to perform to make the array $a$ good. It can be shown that this is always possible.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 500$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 100$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($a_i = \pm 1$) — the elements of the array $a$.

Output

For each test case, output a single integer — the minimum number of operations that need to be done to make the $a$ array good.

ExampleInput

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

Output

1
1
0
3
0
1
2

Note

In the first test case, we can assign the value $a_1 := 1$. Then $a_1 + a_2 + a_3 + a_4 = 1 + (-1) + 1 + (-1) = 0 \ge 0$ and $a_1 \cdot a_2 \cdot a_3 \cdot a_4 = 1 \cdot (-1) \cdot 1 \cdot (-1) = 1$. Thus, we performed $1$ operation.

In the second test case, we can assign $a_1 := 1$. Then $a_1 + a_2 + a_3 + a_4 + a_5 = 1 + (-1) + (-1) + 1 + 1 = 1 \ge 0$ and $a_1 \cdot a_2 \cdot a_3 \cdot a_4 \cdot a_5 = 1 \cdot (-1) \cdot (-1) \cdot 1 \cdot 1 = 1$. Thus, we performed $1$ operation.

In the third test case, $a_1 + a_2 + a_3 + a_4 = (-1) + 1 + (-1) + 1 = 0 \ge 0$ and $a_1 \cdot a_2 \cdot a_3 \cdot a_4 = (-1) \cdot 1 \cdot (-1) \cdot 1 = 1$. Thus, all conditions are already satisfied and no operations are needed.

In the fourth test case, we can assign the values $a_1 := 1, a_2 := 1, a_3 := 1$. Then $a_1 + a_2 + a_3 = 1 + 1 + 1 = 3 \ge 0$ and $a_1 \cdot a_2 \cdot a_3 = 1 \cdot 1 \cdot 1 = 1$. Thus, we performed $3$ operations.

题目大意：
给定一个长度为n的数组a，其元素等于-1和1。如果以下条件同时满足，则称数组a为“好的”：
- a[1] + a[2] + ... + a[n] ≥ 0;
- a[1] * a[2] * ... * a[n] = 1。
每次操作可以选择数组的任意元素a[i]并将其值更改为相反的值。换句话说，如果a[i] = -1，你可以将其赋值为a[i] := 1，如果a[i] = 1，则赋值为a[i] := -1。
确定需要执行的最小操作数以使数组a变好。可以证明这总是可能的。

输入输出数据格式：
输入：
每个测试用例由多个测试组成。第一行包含一个整数t（1 ≤ t ≤ 500）——测试用例的数量。接下来是测试用例的描述。
每个测试用例的第一行包含一个整数n（1 ≤ n ≤ 100）——数组a的长度。
每个测试用例的第二行包含n个整数a[1], a[2], ..., a[n]（a[i] = ±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 ≥ 0且a[1] * a[2] * a[3] * a[4] = 1 * (-1) * 1 * (-1) = 1。因此，我们执行了1次操作。
在第二个测试用例中，我们可以将a[1]赋值为1。然后a[1] + a[2] + a[3] + a[4] + a[5] = 1 + (-1) + (-1) + 1 + 1 = 1 ≥ 0且a[1] * a[2] * a[3] * a[4] * a[5] = 1 * (-1) * (-1) * 1 * 1 = 1。因此，我们执行了1次操作。
在第三个测试用例中，a[1] + a[2] + a[3] + a[4] = (-1) + 1 + (-1) + 1 = 0 ≥ 0且a[1] * a[2] * a[3] * a[4] = (-1) * 1 * (-1) * 1 = 1。因此，所有条件已经满足，不需要操作。
在第四个测试用例中，我们可以将a[1] := 1, a[2] := 1, a[3] := 1。然后a[1] + a[2] + a[3] = 1 + 1 + 1 = 3 ≥ 0且a[1] * a[2] * a[3] = 1 * 1 * 1 = 1。因此，我们执行了3次操作。题目大意： 给定一个长度为n的数组a，其元素等于-1和1。如果以下条件同时满足，则称数组a为“好的”： - a[1] + a[2] + ... + a[n] ≥ 0; - a[1] * a[2] * ... * a[n] = 1。 每次操作可以选择数组的任意元素a[i]并将其值更改为相反的值。换句话说，如果a[i] = -1，你可以将其赋值为a[i] := 1，如果a[i] = 1，则赋值为a[i] := -1。 确定需要执行的最小操作数以使数组a变好。可以证明这总是可能的。 输入输出数据格式： 输入： 每个测试用例由多个测试组成。第一行包含一个整数t（1 ≤ t ≤ 500）——测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含一个整数n（1 ≤ n ≤ 100）——数组a的长度。 每个测试用例的第二行包含n个整数a[1], a[2], ..., a[n]（a[i] = ±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 ≥ 0且a[1] * a[2] * a[3] * a[4] = 1 * (-1) * 1 * (-1) = 1。因此，我们执行了1次操作。 在第二个测试用例中，我们可以将a[1]赋值为1。然后a[1] + a[2] + a[3] + a[4] + a[5] = 1 + (-1) + (-1) + 1 + 1 = 1 ≥ 0且a[1] * a[2] * a[3] * a[4] * a[5] = 1 * (-1) * (-1) * 1 * 1 = 1。因此，我们执行了1次操作。 在第三个测试用例中，a[1] + a[2] + a[3] + a[4] = (-1) + 1 + (-1) + 1 = 0 ≥ 0且a[1] * a[2] * a[3] * a[4] = (-1) * 1 * (-1) * 1 = 1。因此，所有条件已经满足，不需要操作。 在第四个测试用例中，我们可以将a[1] := 1, a[2] := 1, a[3] := 1。然后a[1] + a[2] + a[3] = 1 + 1 + 1 = 3 ≥ 0且a[1] * a[2] * a[3] = 1 * 1 * 1 = 1。因此，我们执行了3次操作。