Problem Description

Author: eedwang

Snowdrop本人給大家參考一下

Snowdrop 收藏了 n 個不同的玩偶，每個玩偶可能以下三種之一: - gura的玩偶（代表數值-1 - saba的玩偶（代表數值0 - fubuki的玩偶（代表數值1

Snowdrop 可以對任何一個玩偶施展魔法，每次魔法會讓該玩偶： -如果施法對象是gura玩偶則變成saba玩偶 -如果施法對象是saba玩偶則變成fubuki玩偶 -如果施法對象是fubuki玩偶則不變

Snowdrop 希望他的所有玩偶能彼此和諧，也就是這些玩偶的狀態值相乘後，結果要嚴格大於 0。 他想知道，最少需要施展幾次魔法，才能達成這個目標。

保證一定可以做到。

Input Format

第一行：一個整數 t (1 ≤ t ≤ 10⁴)，表示測資數量 對於每個測資： 第一行：一個整數 n (1 ≤ n ≤ 8)，表示玩偶的數量 第二行：n 個整數 a₁,a₂,…,a_n（−1 ≤ a_i ≤ 1），代表每個玩偶是哪種玩偶

Output Format

對於每個情境，輸出一個整數，表示 Snowdrop 最少需要施展幾次魔法才能讓結果嚴格大於 0

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

3
1
4