Polycarp has n friends, the i-th of his friends has a_i candies. Polycarp's friends do not like when they have different numbers of candies. In other words they want all a_i to be the same. To solve this, Polycarp performs the following set of actions exactly once: 

  * Polycarp chooses k (0 ≤ k ≤ n) arbitrary friends (let's say he chooses friends with indices i_1, i_2, …, i_k); 
  * Polycarp distributes their a_{i_1} + a_{i_2} + … + a_{i_k} candies among all n friends. During distribution for each of a_{i_1} + a_{i_2} + … + a_{i_k} candies he chooses new owner. That can be any of n friends. Note, that any candy can be given to the person, who has owned that candy before the distribution process. 



Note that the number k is not fixed in advance and can be arbitrary. Your task is to find the minimum value of k.

For example, if n=4 and a=[4, 5, 2, 5], then Polycarp could make the following distribution of the candies: 

  * Polycarp chooses k=2 friends with indices i=[2, 4] and distributes a_2 + a_4 = 10 candies to make a=[4, 4, 4, 4] (two candies go to person 3). 



Note that in this example Polycarp cannot choose k=1 friend so that he can redistribute candies so that in the end all a_i are equal.

For the data n and a, determine the minimum value k. With this value k, Polycarp should be able to select k friends and redistribute their candies so that everyone will end up with the same number of candies.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4). Then t test cases follow.

The first line of each test case contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5).

The second line contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 10^4).

It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10^5.

Output

For each test case output: 

  * the minimum value of k, such that Polycarp can choose exactly k friends so that he can redistribute the candies in the desired way; 
  * "-1" if no such value k exists. 

Example

Input


5
4
4 5 2 5
2
0 4
5
10 8 5 1 4
1
10000
7
1 1 1 1 1 1 1


Output


2
1
-1
0
0
import math 
from collections import Counter, defaultdict
import sys
# resource.setrlimit(resource.RLIMIT_STACK, (2**29,-1))
# sys.setrecursionlimit(10**6)

"""
# Template Designed By: Shivshanker Singh
# Note: If you find this template useful and want to use it then please don't just copy paste it 
        you can take ideas from this and make your own.
        because if you copy paste as it is then there are high chances that both of us will be plagiarized
        (because most of code will be same for small problems).
        So to avoid this please dont copy paste.
"""

mod       = 10**9 + 7
input     = sys.stdin.readline
readInt   = lambda : int(input().strip())
readfloat = lambda : float(input().strip())
readStr   = lambda : input().strip()
intList   = lambda : list(map(int, input().strip().split()))
intMap    = lambda : map(int, input().strip().split())
floatList = lambda : list(map(float, input().strip().split()))
floatMap  = lambda : map(float, input().strip().split())
strList   = lambda : list(input().strip().split())


def print(*args, end='\n', sep=' '):
    for i in args:
        sys.stdout.write(str(i))
        sys.stdout.write(sep)
    sys.stdout.write(end)


def solve(arr):
    avg = sum(arr)/n
    if avg != int(avg):
        return -1
    res = 0
    for i in arr:
        res += max(0, avg-i)
    arr.sort(reverse= True)
    k = 0
    req_sum = 0
    # print(res, avg)
    for i in arr:
        if req_sum == res:
            return k
        k += 1
        req_sum += i - avg


    
# if __name__ == '__main__':
for _ in range(readInt()):
    n = readInt()
    # a, b = intMap()
    arr = intList()
    # print('YES' if solve() else 'NO')
    print(solve(arr))