Problem Statement

Define the score of a non-empty integer sequence $x = (x_1, \ldots, x_n)$ as the number of elements of $x$ that are strictly greater than the average of $x$.

That is, the score of $x$ is the count of indices $i$ satisfying $x_i > \dfrac{x_1+\cdots+x_n}{n}$.

You are given a length-$N$ integer sequence $A = (A_1, \ldots, A_N)$. Find the maximum score of a non-empty subsequence of $A$.

There are $T$ test cases; solve each one.

Definition of subsequence A subsequence of $A$ is any sequence obtained by deleting zero or more elements from $A$ and keeping the remaining elements in their original order.

Constraints

• $1\le T\le 2\times 10^5$
• $2\le N\le 2\times 10^5$
• $1\le A_i\le 10^9$
• All input values are integers.
• The sum of $N$ over all test cases is at most $2\times 10^5$.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\vdots
\text{case}_T

Each case is given in the following format:

N
A_1 \cdots A_N

Output

Print $T$ lines. The $i$-th line should contain the maximum score of a non-empty subsequence of $A$ for the $i$-th test case.