Guards in ISM work really hard to provide the top class security to students ;-) ISM Administration also knows this. So they decided to give some money to the guards. They gave some amount of money to all the guards, but some guards became really angry after this since they got less money than others. So Administration thought to distribute the money to the guards such that each guard gets equal amount of money. They used a particular algorithm to do this. At every step, if guard A has maximum amount of money (say “X”) and guard B has minimum amount of money (say “Y”), they transfer LIF((X-Y)/2) amount of money from A to B. LIF(x) returns the least integer that is not less than x. They repeat this until everyone gets equal amount of money. Can you tell ISM Administration in how many steps they will be able to distribute this money equally? Print “-1” without quotes if it is not possible to distribute money equally by this algorithm.

Input

First line of the input will contain “T”, the number of test cases. For each test case, there will be two lines of input. The first line will contain “N”, the number of guards in ISM. The next line will contain N integers A[i] denoting the initial amount of money given to each guard.

Output

For each test case print an integer denoting the minimum number of steps required to distribute the money equally among all the guards using the above mentioned algorithm. Print “-1” without quotes if it is not possible to distribute the money equally.

Constraints

1 <= T <= 10

1 <= N <= 2000

0 <= A[i] <= N

Example

Input:
3
2
3 2
4
1 5 5 9
5
1 2 3 4 5

Output:
-1
1
2