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 java.io.*;
import java.util.*;

public class Solution {

	static long modInverse(long a, long m) {
		long m0 = m;
		long y = 0, x = 1;

		if (m == 1)
			return 0;

		while (a > 1) {

			long q = a / m;

			long t = m;

			m = a % m;
			a = t;
			t = y;

			y = x - q * y;
			x = t;
		}

		if (x < 0)
			x += m0;

		return x;
	}

	static void pla() {

		int a = 0;
		int b = 2;
		int c = 0;
		int d = 0;

		a = (int) Math.pow(2, 32);

		c = a + b;
		b = c / a;
		d = a + b + c;

	}

	static int mod = (int) 1e9 + 7;

	static Scanner sc = new Scanner(System.in);
	static StringBuilder out = new StringBuilder();

	

	public static void main(String[] args) throws IOException {

		int t = sc.nextInt();

		
		int tc = 1;
		while (tc <= t) {

			// out.append("Case #" + tc + ": ");
			Solution run = new Solution();

			run.run();

			tc++;
		}

		System.out.println(out);

	}

	
	public static int gcd(int a, int b) {
		return (b == 0) ? a : gcd(b, a % b);
	}

	public void run() throws IOException {
		
		
		int n=sc.nextInt();
		long a[]=new long[n];
		
		
		long sum=0;
		
		
		for(int i=0;i<n;i++) {
			
			a[i]=sc.nextInt();
			
			sum+=(long)a[i];
		}
		
		if(sum%n!=0) {
			
			out.append(-1+"\n");
		}
		else {
			
			sum/=(long)n;
			
			int ans=0;
			for(int i=0;i<n;i++) {
				
				if(a[i]>sum)ans++;
			}
			
			out.append(ans+"\n");
			
		}
	}
	
	
	static void sort(int a[], int n) {

		ArrayList<Integer> al = new ArrayList<>();

		for (int i = 0; i < n; i++) {

			al.add(a[i]);
		}

		Collections.sort(al);

		for (int i = 0; i < n; i++) {

			a[i] = al.get(i);
		}
	}

	static void sort(long a[], int n) {

		ArrayList<Long> al = new ArrayList<>();

		for (int i = 0; i < n; i++) {

			al.add(a[i]);
		}

		Collections.sort(al);

		for (int i = 0; i < n; i++) {

			a[i] = al.get(i);
		}
	}

	static Reader scn = new Reader();

	static class Reader {
		final private int BUFFER_SIZE = 1 << 16;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;

		public Reader() {
			din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public Reader(String file_name) throws IOException {
			din = new DataInputStream(new FileInputStream(file_name));
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public String readLine() throws IOException {
			byte[] buf = new byte[64]; // line length
			int cnt = 0, c;
			while ((c = read()) != -1) {
				if (c == '\n')
					break;
				buf[cnt++] = (byte) c;
			}
			return new String(buf, 0, cnt);
		}

		public int nextInt() throws IOException {
			int ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (neg)
				return -ret;
			return ret;
		}

		public long nextLong() throws IOException {
			long ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}

		public double nextDouble() throws IOException {
			double ret = 0, div = 1;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();

			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (c == '.') {
				while ((c = read()) >= '0' && c <= '9') {
					ret += (c - '0') / (div *= 10);
				}
			}

			if (neg)
				return -ret;
			return ret;
		}

		private void fillBuffer() throws IOException {
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1)
				buffer[0] = -1;
		}

		private byte read() throws IOException {
			if (bufferPointer == bytesRead)
				fillBuffer();
			return buffer[bufferPointer++];
		}

		public void close() throws IOException {
			if (din == null)
				return;
			din.close();
		}
	}

}