A. Eshag Loves Big Arrays

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Eshag has an array aa consisting of nn integers.

Eshag can perform the following operation any number of times: choose some subsequence of aa and delete every element from it which is strictly larger than AVGAVG, where AVGAVG is the average of the numbers in the chosen subsequence.

For example, if a=[1,4,3,2,4]a=[1,4,3,2,4] and Eshag applies the operation to the subsequence containing a1a1, a2a2, a4a4 and a5a5, then he will delete those of these 44 elements which are larger than a1+a2+a4+a54=114a1+a2+a4+a54=114, so after the operation, the array aa will become a=[1,3,2]a=[1,3,2].

Your task is to find the maximum number of elements Eshag can delete from the array aa by applying the operation described above some number (maybe, zero) times.

A sequence bb is a subsequence of an array cc if bb can be obtained from cc by deletion of several (possibly, zero or all) elements.

Input

The first line contains an integer tt (1≤t≤100)(1≤t≤100) — the number of test cases. The description of the test cases follows.

The first line of each test case contains an integer nn (1≤n≤100)(1≤n≤100) — the length of the array aa.

The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤100)(1≤ai≤100) — the elements of the array aa.

Output

For each test case print a single integer — the maximum number of elements Eshag can delete from the array aa.

Example

input

Copy

3
6
1 1 1 2 2 3
6
9 9 9 9 9 9
6
6 4 1 1 4 1

output

Copy

3
0
3

Note

Consider the first test case.

Initially a=[1,1,1,2,2,3]a=[1,1,1,2,2,3].

In the first operation, Eshag can choose the subsequence containing a1a1, a5a5 and a6a6, their average is equal to a1+a5+a63=63=2a1+a5+a63=63=2. So a6a6 will be deleted.

After this a=[1,1,1,2,2]a=[1,1,1,2,2].

In the second operation, Eshag can choose the subsequence containing the whole array aa, the average of all its elements is equal to 7575. So a4a4 and a5a5 will be deleted.

After this a=[1,1,1]a=[1,1,1].

In the second test case, Eshag can't delete any element.

解题说明：此题是一道数学题，先找出数列中最小的数字，然后遍历判断数列，每次选择最小值和另一个数字，判断是否超过均值，这样就能保证删除尽可能多的数字。

#include<stdio.h>

int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		int n, min, count = 0;
		scanf("%d", &n);
		int a[108];
		scanf("%d", &a[0]);
		min = a[0];
		for (int i = 1; i<n; i++)
		{
			scanf("%d", &a[i]);
			if (min > a[i])
			{
				min = a[i];
			}
		}
		for (int i = 0; i<n; i++)
		{
			if (a[i] > min)
			{
				count++;
			}
		}
		printf("%d\n", count);
	}
}