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 的數(shù)組 a，其中元素等于 -1

? 1. 如果同時滿足以下條件，我們稱該數(shù)組為好數(shù)組：

a1+a2+…+an≥0；

a1·a2·…·an=1。

在一次操作中，您可以選擇數(shù)組 ai 的任意元素

? 并將其值更改為相反的值。 換句話說，如果ai=?1，則可以將值賦給ai:=1，如果ai=1，則可以將值賦給ai:=?1。

確定使數(shù)組良好所需執(zhí)行的最少操作數(shù)。 可以證明這總是可能的。

輸入

每個測試由多個測試用例組成。 第一行包含一個整數(shù) t (1≤t≤500) — 測試用例的數(shù)量。 測試用例的描述如下。

每個測試用例的第一行包含一個整數(shù)n（1≤n≤100）——數(shù)組a的長度。

每個測試用例的第二行包含 n 個整數(shù) a1,a2,…,an (ai=±1) — 數(shù)組 a 的元素。

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

分兩步，第一步將sum轉(zhuǎn)成正數(shù)，然后再去判斷乘積是否>0,如果乘積大于0，返回即可，如果小于0，則+1返回、

下面是代碼：