$n$ integers are arranged in a circle. An operation is defined as follows: choose an integer $a$ from the circle, replace it with $-a$, and add $a$ to its two adjacent neighbors on the circle.

Find the minimum number of operations required to make all integers non-negative.

Input

There are multiple test cases.

The first line contains a positive integer $T$ ($1 \leq T \leq 10$), representing the number of test cases.

For each test case, there are two lines:

• The first line contains a positive integer $n$ ($3 \leq n \leq 10^5$).
• The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($-10^4 \leq a_i \leq 10^4$), which are arranged in a circle in order.

Output

For each test case, output a single integer on a new line. If it is possible to make all integers non-negative, output the minimum number of operations; otherwise, output $-1$.

Examples

Input 1

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

Output 1

5
-1
0

Note

For the initial state $2, 2, -3$, the sequence of operations is: $2, 2, -3 \Longrightarrow -1, -1, 3 \Longrightarrow 1, -2, 2 \Longrightarrow -1, 2, 0 \Longrightarrow 1, 1, -1 \Longrightarrow 0, 0, 1$. The goal is reached in $5$ operations, and it is clear that no fewer operations are possible.

For the initial state $2, 2, -5$, it is impossible to reach the goal.

For the initial state $0, 0, 0$, the goal is already reached without any operations.

Subtasks

• Task 1 (10 points): $n = 3$, $-10 \leq a_i \leq 10$.
• Task 2 (20 points): $n \leq 50$, $-10 \leq a_i \leq 10$.
• Task 3 (30 points): $n \leq 2\,000$.
• Task 4 (10 points): $n \leq 3 \times 10^4$, $\sum a_i = 1$.
• Task 5 (10 points): $n \leq 3 \times 10^4$, $-10 \leq \sum a_i \leq 10$.
• Task 6 (10 points): $n \leq 3 \times 10^4$.
• Task 7 (10 points): No additional constraints.

For $100\%$ of the data, $1 \leq T \leq 10$, $3 \leq n \leq 10^5$, $-10^4 \leq a_i \leq 10^4$.