Yuki has a sequence $a$ of length $n$.

Yuki defines an operation as follows:

• Choose an interval $[l, r]$ of even length. For every integer $i$ such that $l \le i \le r$:
  • If $i - l$ is odd, the value of $a_i$ decreases by $1$, i.e., $a_i \leftarrow a_i - 1$.
  • If $i - l$ is even, the value of $a_i$ increases by $1$, i.e., $a_i \leftarrow a_i + 1$.

Now, Yuki wants to perform some number of operations such that all numbers in the sequence $a$ are equal. You need to help Yuki find the minimum number of operations required to make all numbers in the sequence $a$ equal, or report if it is impossible.

Input

This problem contains multiple test cases.

The first line contains a positive integer $t$ ($1 \le t \le 10^5$), representing the number of test cases.

For each test case:

• The first line contains a positive integer $n$ ($1 \le n \le 10^6$).
• The second line contains $n$ integers $a_1, \dots, a_n$ ($0 \le a_i \le 10^{12}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

Output

For each test case, output one line:

• If it is impossible, output $-1$.
• If it is possible, output an integer representing the minimum number of operations to make all numbers in the sequence $a$ equal.

Examples

Input 1

3
2
1 3
4
1 5 1 5
5
1 3 1 3 1

Output 1

1
2
-1

Note

For the first test case:

• Perform the operation on the interval $[1, 2]$. The sequence becomes $2, 2$, where all numbers are equal.
• It can be proven that no solution with fewer operations exists, so the answer is $1$.

For the second test case:

• Perform the operation on the interval $[1, 4]$. The sequence becomes $2, 4, 2, 4$.
• Perform the operation on the interval $[1, 4]$. The sequence becomes $3, 3, 3, 3$, where all numbers are equal.
• It can be proven that no solution with fewer operations exists, so the answer is $2$.

For the third test case:

• It is easy to prove that it is impossible to make all numbers equal regardless of the number of operations, so the answer is $-1$.