$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$。