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

public class cf {
	static Reader sc = new Reader();
	static PrintWriter out = new PrintWriter(System.out);

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

	public static void main(String[] args) {
		int t = sc.ni();
		while (t-- > 0) {
			int n = sc.ni();
			int[] arr = sc.nai(n);
			Arrays.sort(arr);
			int sum = 0;
			for (int e : arr)
				sum += e;
			if (sum % n != 0) {
				out.println(-1);
				continue;
			}
			int l = 0, r = n, res = -1;
			while (l <= r) {
				int mid = l + (r - l) / 2;
				if (good(mid, arr, sum)) {
					res = mid;
					r = mid - 1;
				} else {
					l = mid + 1;
				}
			}
			out.println(res);
		}
		out.close();
	}

	static boolean good(int x, int[] arr, int sum) {
		int split = sum / arr.length;
		int lastSum = 0;
		for (int i = arr.length - 1; i >= arr.length - x; i--) {
			lastSum += arr[i];
		}
		lastSum -= x * split;
		for (int i = 0; i < arr.length - x; i++) {
			if (arr[i] > split)
				return false;
			if (arr[i] < split) {
				int diff = split - arr[i];
				if (lastSum < diff)
					return false;
				lastSum -= diff;
				arr[i] = split;
			}
		}
		return true;
	}

	static int gcd(int a, int b) {
		if (b == 0)
			return a;
		return gcd(b, a % b);
	}

	static void shuffleSort(int[] arr) {
		// shuffle
		Random rand = new Random();
		for (int i = 0; i < arr.length; i++) {
			int j = rand.nextInt(i + 1);
			int tmp = arr[i];
			arr[i] = arr[j];
			arr[j] = tmp;
		}
		Arrays.sort(arr);
	}

	static ArrayList<Integer> sieve(int n) {
		ArrayList<Integer> primes = new ArrayList<>();
		boolean[] isPrime = new boolean[n];
		Arrays.fill(isPrime, true);
		isPrime[0] = isPrime[1] = false;
		for (int i = 2; i * i <= n; i++) {
			if (isPrime[i]) {
				for (int j = i * i; j < n; j += i) {
					isPrime[j] = false;
				}
			}
		}
		for (int i = 2; i < n; i++) {
			if (isPrime[i])
				primes.add(i);
		}
		return primes;
	}

	static class Reader {
		BufferedReader br;
		StringTokenizer st;

		Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
			st = new StringTokenizer("");
		}

		Reader(File f) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(f));
			st = new StringTokenizer("");
		}

		String next() {
			while (!st.hasMoreTokens())
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
				}
			return st.nextToken();
		}

		int ni() {
			return Integer.parseInt(next());
		}

		long nl() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		int[] nai(int n) {
			int[] a = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = ni();
			return a;
		}

		long[] nal(int n) {
			long[] a = new long[n];
			for (int i = 0; i < n; i++)
				a[i] = nl();
			return a;
		}

		char[][] nmc(int n, int m) {
			char[][] map = new char[n][m];
			for (int i = 0; i < n; i++) {
				String str = sc.next();
				for (int j = 0; j < m; j++) {
					map[i][j] = str.charAt(j);
				}
			}
			return map;
		}

		int[][] nmi(int n, int m) {
			int[][] map = new int[n][m];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					map[i][j] = ni();
				}
			}
			return map;
		}

		long[][] nml(int n, int m) {
			long[][] map = new long[n][m];
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					map[i][j] = nl();
				}
			}
			return map;
		}
	}

}