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.util.*;
import java.util.Map.Entry;
import java.io.*;
import java.text.DecimalFormat;
		
public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		int t=sc.nextInt();
		while(t-->0) {
		int k=sc.nextInt();
		int [] arr = new int[k];
		int sum=0;
		for(int j=0;j<k;j++) {
			arr[j]=sc.nextInt();
			sum+=arr[j];
		}
		if(sum%k!=0) {
			System.out.println(-1);
		}else {
			int n=0;
			for(int i=0;i<k;i++) {
				if(arr[i]>(sum/k)) {
					n++;
				}
			}
			System.out.println(n==0?0:n);
		}
		
		
			
			
		
		
		}
		
	}
	
	
	
	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(FileReader f) {
			br = new BufferedReader(f);
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}
}
