Did you know that Chwee kueh, a cuisine of Singapore, means water rice cake ? Its a variety of the most popular South Indian savory cake, only that we call it here idli :). The tastiest idlis are made in Chennai, by none other than our famous chef, Dexter Murugan. Being very popular, he is flown from Marina to Miami, to serve idlis in the opening ceremony of icpc world finals ( which is happening right now ! ).
There are N students and they are initially served with some idlis. Some of them are angry because they got less idlis than some other. Dexter decides to redistribute the idlis so they all get equal number of idlis finally. He recollects his father's code, "Son, if you ever want to redistribute idlis, follow this method. While there are two persons with unequal number of idlis, repeat the following step. Select two persons A and B,  A having the maximum and B having the minimum number of idlis, currently. If there are multiple ways to select A (similarly B), select any one randomly. Let A and B have P and Q number of idlis respectively and R = ceil( ( P - Q ) / 2 ), Transfer R idlis from A to B."
Given the initial number of idlis served to each student, find the number of times Dexter has to repeat the above step. If he can not distribute idlis equally by following the above method, print -1.


Notes ceil(x) is the smallest integer that is not less than x.


Input
First line contains an integer T ( number of test cases, around 20 ). T cases follows. Each case starts with an integer N ( 1 <= N <= 3000 ). Next line contains an array A of N integers separated by spaces, the initial number of idlis served ( 0 <= A[i] <= N )


Output
For each case, output the number of times Dexter has to repeat the given step to distribute idlis equally or -1 if its not possible.


Example

Input:
3
4
1 2 2 3
2
1 2
7
1 2 3 4 5 6 7
Output:
1
-1
3

Explanation:
Case 1 : { 1, 2, 2, 3}. Maximum 3, Minimum 1. R = ceil((3-1)/2) = 1. Transfer 1 idli from person having 3 idlis to the person having 1 idli. Each of them has 2 idlis now, so just 1 step is enough.
Case 2 : {1,2} R = ceil((2-1)/2) = 1. {1,2} -> {2,1} -> {1,2} .... they can never get equal idlis :(
Case 3 : Sorted arrays, in the order encountered {1, 2, 3, 4, 5, 6, 7} -> {2, 3, 4, 4, 4, 5, 6} -> {3, 4, 4, 4, 4, 4, 5} -> {4, 4, 4, 4, 4, 4, 4}

NoteThere are multiple test sets, and the judge shows the sum of the time taken over all test sets of your submission, if Accepted. Time limit on each test set is 3 sec
import heapq

from math import ceil

t = int(raw_input())

def test(L):
    fault = True
    for x in range(len(L) - 1):
        if L[x] != L[x + 1]: fault = False
    return fault
    
##
##def processor(L):
##    S = sum(L)
##    if S % len(L) != 0: print -1
##    elif test(L): print 0
##    else:
##        acc = 0
##        small = []
##        large = []
##        for x in L:
##            heapq.heappush(small, x)
##            heapq.heappush(large, int(-1 * x))
##        while True:
##            s = heapq.heappop(small)
##            l = int(-1 * heapq.heappop(large))
##            
##            if s == l: break
##            else:
##                val = ceil((l - s)/ 2.0)
##                s_mod = s + val
##                l_mod = l - val
##                #go in small and find l. replace that with l_mod. heapify
##                for x in range(len(small)):
##                    if small[x] == l:
##                        small[x] = l_mod
##                        break
##                heapq.heapify(small)
##                heapq.heappush(small, s_mod)
##                #go in large and find s. replace that with s_mod. heapify
##                for x in range(len(large)):
##                    if int(-1 * large[x]) == s:
##                        large[x] = int( -1 * s_mod)
##                        break
##                heapq.heapify(large)
##                heapq.heappush(large, int(-1 * l_mod))
##                acc += 1
##        print acc
##

            
                
def processor(L):
    S = sum(L)
    if S % len(L) != 0: print -1
    elif test(L): print 0
    else:
        acc = 0
        small = []
        large = []
        needs = S / len(L)
        for x in L:
            if x < needs: heapq.heappush(small, x)
            else: heapq.heappush(large, int(-1 * x))
        fault = False
        while True:
            if len(small) == 0 and len(large) != 0:
                l = int(-1 * heapq.heappop(large))
                if l == needs: break
                else:
                    fault = True
                    break
            if len(small) != 0 and len(large) == 0:
                s = heapq.heappop(small)
                if s == needs: break
                else:
                    fault = True
                    break
            s = heapq.heappop(small)
            l = int(-1 * heapq.heappop(large))
            if s == l: break
            else:
                val = ceil((l - s)/2.0)
                l_mod = l - val
                s_mod = s + val
                if l_mod > needs: heapq.heappush(large, int(-1 * l_mod))
                else: heapq.heappush(small, l_mod)
                if s_mod > needs: heapq.heappush(large, int(-1 * s_mod))
                else: heapq.heappush(small, s_mod)
                acc += 1
        if fault: print -1
        else: print acc
            

for i in range(t):
    raw_input()
    processor([int(x) for x in raw_input().split()])