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 sys

# taking input as string
input = lambda: sys.stdin.readline().rstrip("\r\n")
inp = lambda: list(map(int, sys.stdin.readline().rstrip("\r\n").split()))
mod = 10 ** 9 + 7;
Mod = 998244353;
INF = float('inf')
# ______________________________________________________________________________________________________
from math import *
from bisect import *
from heapq import *
from functools import *
from collections import defaultdict as dd
from collections import OrderedDict as odict
from collections import Counter as cc
from collections import deque
from itertools import *

sys.setrecursionlimit(20 * 20 * 20 * 20 + 10)  # this is must for dfs
MAX = 10 ** 5
# teaverse list in reverse order = for i in range(n-1, -1, -1)

############################### my code here ####################################
def solve():
    n = takeint()
    arr = takeiarr()
    if n == 1:print(0)
    if arr.count(arr[0]) == n and n!= 1:print(0)
    if arr.count(arr[0]) != n:
        total = sum(arr)
        if total % n != 0:print(-1)
        else:
            each = total // n
            count = 0

            for i in range(n):
                if arr[i] > each:count += 1
                else:pass
            print(count)



def main():
    global tt

    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt", "r")
        sys.stdout = open("output.txt", "w")
    t = 1
    t = takeint()
    for tt in range(1, t + 1):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :", time.time() - start_time, "seconds")
        sys.stdout.close()


# ---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
# input the integer
def takeint():
    return (int(sys.stdin.readline().rstrip("\r\n")))


# input the string
def takestr():
    return (sys.stdin.readline().rstrip("\r\n"))


# input int array
def takeiarr():
    return (list(map(int, sys.stdin.readline().rstrip("\r\n").split())))


# input string array
def takesarr():
    return (list(map(str, sys.stdin.readline().rstrip("\r\n").split())))


# innut values for the diffrent variables
def takeivar():
    return (map(int, sys.stdin.readline().rstrip("\r\n").split()))


def takesvar():
    return (map(str, sys.stdin.readline().rstrip("\r\n").split()))


# ------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#


def ispalindrome(s):
    return s == s[::-1]


def invert(bit_s):
    # convert binary string
    # into integer
    temp = int(bit_s, 2)

    # applying Ex-or operator
    # b/w 10 and 31
    inverse_s = temp ^ (2 ** (len(bit_s) + 1) - 1)

    # convert the integer result
    # into binary result and then
    # slicing of the '0b1'
    # binary indicator
    rslt = bin(inverse_s)[3:]

    return str(rslt)


def swap(a, b):
    a, b = b, a
    return a, b


def counter(a):
    # create a list of frequency of each element in a
    # [2,3,2,1] -> [1,2,1]

    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return (q)


def counter_elements(a):
    # dictionary of frequency of elements
    q = dict()
    for i in range(len(a)):
        if a[i] not in q:
            q[a[i]] = 0
        q[a[i]] = q[a[i]] + 1
    return (q)


def string_counter(a):
    # returns list of frequency of each alphabet in given string
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97] + 1
    return (q)


def factorial(n):
    # for very large numbers
    dp = [1] * (n + 1)

    for i in range(1, n + 1):
        dp[i] = dp[i - 1] * i
    return dp[n]

def isSubSequence(string1, string2, m, n):
       # Base Cases
    if m == 0:
           return True
    if n == 0:
           return False

        # If last characters of two
        # strings are matching
    if string1[m - 1] == string2[n - 1]:
           return isSubSequence(string1, string2, m - 1, n - 1)

        # If last characters are not matching
    return isSubSequence(string1, string2, m, n - 1)


def factors(n):
    q = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0: q.append(i); q.append(n // i)
    return (list(sorted(list(set(q)))))


def prime_factors(n):
    q = []
    while n % 2 == 0: q.append(2); n = n // 2
    for i in range(3, int(n ** 0.5) + 1, 2):
        while n % i == 0: q.append(i); n = n // i
    if n > 2: q.append(n)
    return (list(sorted(q)))


def transpose(a):
    n, m = len(a), len(a[0])
    b = [[0] * n for i in range(m)]
    for i in range(m):
        for j in range(n):
            b[i][j] = a[j][i]
    return (b)


def power_two(x):
    # returns true if x is a power of 2
    return (x and (not (x & (x - 1))))


def ceil(a, b):
    return -(-a // b)


def seive(n):
    # seive of eratosthenes
    # returns list of all prime numbers <= n

    a = [1]
    prime = [True for i in range(n + 1)]
    p = 2
    while (p * p <= n):
        if (prime[p] == True):
            for i in range(p ** 2, n + 1, p):
                prime[i] = False
        p = p + 1
    for p in range(2, n + 1):
        if prime[p]:
            a.append(p)
    return (a)


def isprime(n):
    if (n > 2 and not n % 2) or n == 1:
        return False

    for i in range(3, int(n ** 0.5 + 1), 2):
        if not n % i:
            return False

    return True

# binary exponentiation
def binexp(a, b):
    if b == 0:
        return 1
    ans = binexp(a, b//2)
    if(b%2):
        return ans*ans*a
    else:
        return ans * ans

def most_frequent(nums):
    # most frequent element in a list
    return max(set(nums), key = nums.count)


def binary_search(nums, target):
    # nums must be already sorted
    low, high = 0, len(nums) - 1

    # returns -1 if element not found
    while low <= high:
        mid = (low + high) // 2
        if nums[mid] == target:return mid + 1
        if nums[mid] > target:high = mid - 1
        else:low = mid + 1
    return -1

def lcm(numbers):
    # list of numbers whose lcm is to be found
    return reduce((lambda x, y: int(x * y / gcd(x, y))), numbers)

def gcd(a, b):
    while(b): a, b = b, a % b
    return a
# -----------------------------------------------------------------------#
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline

main()