$n$ 个整数排成一圈，定义一次操作为：选择其中一个整数 $a$，将其变为 $-a$，并使圈上与其相邻的两个整数加上 $a$。

求至少操作几次，可以使所有整数均变为非负的。

输入格式

有多组测试数据。

第一行，一个正整数 $T$（$1 \leq T \leq 10$），表示测试数据组数。

对于每组测试数据，有两行：

• 第一行，一个正整数 $n$（$3 \leq n \leq 10^5$）。
• 第二行，$n$ 个整数 $a_1, a_2, \cdots, a_n$（$-10^4 \leq a_i \leq 10^4$），这些整数按顺序排成一圈。

输出格式

对于每组测试数据，仅一行一个整数。如果能够使所有整数均变为非负的，输出最小的操作次数；如果不能，则输出 $-1$。

样例数据

样例输入

3
3
2 2 -3
3
2 2 -5
3
0 0 0

样例输出

5
-1
0

样例解释

初始 $2, 2, -3 \Longrightarrow -1, -1, 3 \Longrightarrow 1, -2, 2 \Longrightarrow -1, 2, 0 \Longrightarrow 1, 1, -1 \Longrightarrow 0, 0, 1$ 达到目标，操作次数为 $5$，且显然无法更优。

初始 $2, 2, -5$，显然无法达到目标。

初始 $0, 0, 0$，无需操作即已经达到目标。

子任务

• 任务 1（10 分）：$n = 3$，$-10 \leq a_i \leq 10$。
• 任务 2（20 分）：$n \leq 50$，$-10 \leq a_i \leq 10$。
• 任务 3（30 分）：$n \leq 2\,000$。
• 任务 4（10 分）：$n \leq 3 \times 10^4$，$\sum a_i = 1$
• 任务 5（10 分）：$n \leq 3 \times 10^4$，$-10 \leq \sum a_i \leq 10$。
• 任务 6（10 分）：$n \leq 3 \times 10^4$。
• 任务 7（10 分）：无特殊条件。

对于 $100\%$ 的数据，$1 \leq T \leq 10$，$3 \leq n \leq 10^5$，$-10^4 \leq a_i \leq 10^4$。