# Andrew and Stones solution codeforces

## Andrew and Stones solution codeforces

Andrew has nn piles with stones. The ii-th pile contains aiai stones. He wants to make his table clean so he decided to put every stone either to the 11-st or the nn-th pile.

Andrew can perform the following operation any number of times: choose 33 indices 1i<j<kn1≤i<j<k≤n, such that the jj-th pile contains at least 22 stones, then he takes 22 stones from the pile jj and puts one stone into pile ii and one stone into pile kk.

Tell Andrew what is the minimum number of operations needed to move all the stones to piles 11 and nn, or determine if it’s impossible.

Input

The input contains several test cases. The first line contains one integer tt (1t100001≤t≤10000) — the number of test cases.

The first line for each test case contains one integer nn (3n1053≤n≤105) — the length of the array.

The second line contains a sequence of integers a1,a2,,ana1,a2,…,an (1ai1091≤ai≤109) — the array elements.

It is guaranteed that the sum of the values nn over all test cases does not exceed 105105.

Output

For each test case print the minimum number of operations needed to move stones to piles 11 and nn, or print 1−1 if it’s impossible.

Example
input

Copy
4
5
1 2 2 3 6
3
1 3 1
3
1 2 1
4
3 1 1 2

output

Copy
4
-1
1
-1

Note

In the first test case, it is optimal to do the following:

1. Select (i,j,k)=(1,2,5)(i,j,k)=(1,2,5). The array becomes equal to [2,0,2,3,7][2,0,2,3,7].
2. Select (i,j,k)=(1,3,4)(i,j,k)=(1,3,4). The array becomes equal to [3,0,0,4,7][3,0,0,4,7].
3. Twice select (i,j,k)=(1,4,5)(i,j,k)=(1,4,5). The array becomes equal to [5,0,0,0,9][5,0,0,0,9]. This array satisfy the statement, because every stone is moved to piles 11 and 55.

There are 44 operations in total.In the second test case, it’s impossible to put all stones into piles with numbers 11 and 33:

1. At the beginning there’s only one possible operation with (i,j,k)=(1,2,3)(i,j,k)=(1,2,3). The array becomes equal to [2,1,2][2,1,2].
2. Now there is no possible operation and the array doesn’t satisfy the statement, so the answer is 1−1.

In the third test case, it’s optimal to do the following:

1. Select (i,j,k)=(1,2,3)(i,j,k)=(1,2,3). The array becomes equal to [2,0,2][2,0,2]. This array satisfies the statement, because every stone is moved to piles 11 and 33.

The is 11 operation in total.In the fourth test case, it’s impossible to do any operation, and the array doesn’t satisfy the statement, so the answer is 1−1.