题目描述

给定一个只包含 1 和 -1 的序列 a（1 ≤ n ≤ 100），当且仅当同时满足以下两个条件时，称 a 是一个 好序列：

1. 序列的和满足：a₁ + a₂ + ... + aₙ ≥ 0
2. 序列的积满足：a₁ × a₂ × ... × aₙ = 1

你可以对序列进行若干次修改，每次可以将 -1 改成 1 或 1 改成 -1。

你的任务是：计算最少需要多少次修改，才能将给定序列变成一个好序列。

输入格式

第一行：一个整数 t（1 ≤ t ≤ 500）— 表示测试用例数量。
接下来 t 组测试用例，每组包含两行：

• 第一行：一个整数 n（1 ≤ n ≤ 100），表示序列长度。
• 第二行：n 个整数，表示序列内容，每个值为 1 或 -1。

输出格式

对于每个测试用例，输出一行，表示将该序列修改为好序列的最少修改次数。

输入样例 #1

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  
1  
0  
3  
0  
1  
2