题目描述

给定长度为 $n$ 的数组 $a$，数组中的每个元素等于 $-1,0$ 或 $1$。在一次操作中，你可以选择一个下标 $i$ 并将 $a_i$ 增加 $1$（即赋值 $a_i := a_i + 1$）。可以对任意下标进行任意次操作。

目标是用最少的操作次数使数组中所有元素的乘积严格为正，即

保证在给定条件下总能达到目标。求使乘积为正所需的最少操作次数。

输入格式

第一行包含一个整数 $t$（$1\le t\le 10^4$），表示测试用例的个数。

随后描述 $t$ 个测试用例，每个测试用例包含两行：

• 第 $1$ 行：整数 $n$（$1\le n\le 8$），表示数组长度。
• 第 $2$ 行：$n$ 个整数 $a_1,a_2,\dots,a_n$，每个 $a_i\in \{-1,0,1\}$，以空格分隔。

输出格式

对于每个测试用例，输出一行，包含一个整数 —— 将数组乘积变为正所需的最少操作次数。

样例输入

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

样例输出

3
1
4

说明

样例解释

• 第一个样例：从 $[-1,0,1]$ 可以通过 $3$ 次操作得到 $[1,1,1]$。
• 第二个样例：只需把 $0\to1$（$1$ 次操作），得到 $[-1,-1,1,1]$，乘积为 $1$。
• 第三个样例：把两个 $0$ 变为 $1$（$2$ 次），再把一个 $-1$ 变为 $1$（需要 $2$ 次），共计 $4$ 次。