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:

a1+a2+…+an≥0;

(相关资料图)

a1⋅a2⋅…⋅an=1.

In one operation, you can select an arbitrary element of the array ai

and change its value to the opposite. In other words, if ai=−1, you can assign the value to ai:=1, and if ai=1, then assign the value to ai:=−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≤t≤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≤n≤100)— the length of the array a.

The second line of each test case contains n integers a1,a2,…,an (ai=±1) — the elements of the array a.

中文：

给定一个长度为 n 的数组 a，其中元素等于 -1

1. 如果同时满足以下条件，我们称该数组为好数组：

a1+a2+…+an≥0；

a1·a2·…·an=1。

在一次操作中，您可以选择数组 ai 的任意元素

并将其值更改为相反的值。 换句话说，如果ai=−1，则可以将值赋给ai:=1，如果ai=1，则可以将值赋给ai:=−1。

确定使数组良好所需执行的最少操作数。 可以证明这总是可能的。

输入

每个测试由多个测试用例组成。 第一行包含一个整数 t (1≤t≤500) — 测试用例的数量。 测试用例的描述如下。

每个测试用例的第一行包含一个整数n（1≤n≤100）——数组a的长度。

每个测试用例的第二行包含 n 个整数 a1,a2,…,an (ai=±1) — 数组 a 的元素。

-----------------------

分两步，第一步将sum转成正数，然后再去判断乘积是否>0,如果乘积大于0，返回即可，如果小于0，则+1返回、

下面是代码：