题目描述

给定一个由 $n$ 个元素组成的数组 $a$ ，其中每个元素都等于 $-1$ 、 $0$ 或 $1$ 。在一次操作中，可以选择索引 $i$ ，并将 $a_i$ 增加 $1$ （即分配 $a_i := a_i + 1$ ）。可以选择任意索引执行任意次数的操作。

我们的目标是用最少的运算次数使数组中所有元素的乘积严格为正，即 $a_1 \cdot a_2 \cdot a_3 \cdot \dots \cdot a_n > 0$ 。求最小的运算次数。

输入格式

每个测试由多个测试用例组成。

第一行包含一个整数 $t$ ( $1 ≤ t ≤ 10^4$ ) 表示测试用例数。

每个测试用例的第一行都包含一个整数 $n$ ( $1 ≤ n ≤ 8$ ) 表示数组 $a$ 的长度

第二行包含 $n$ 个整数 $a_1, a_2, a_3, ..., a_n$ ，其中 $a_i \in \{-1, 0, 1\}$ 表示数组 $a$ 中的元素

输出格式

对于每个测试用例，输出一个整数——使数组中元素的乘积严格为正数所需的最少操作数。

样例

3
3
-1 0 1
4
-1 -1 0 1
5
-1 -1 -1 0 0

3
1
4