Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
B. Friends and Candies

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPolycarp 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 \le k \le n$$$) arbitrary friends (let's say he chooses friends with indices $$$i_1, i_2, \ldots, i_k$$$);
- Polycarp distributes their $$$a_{i_1} + a_{i_2} + \ldots + a_{i_k}$$$ candies among all $$$n$$$ friends. During distribution for each of $$$a_{i_1} + a_{i_2} + \ldots + 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 \le t \le 10^4$$$). Then $$$t$$$ test cases follow.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^4$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 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

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/31/2023 10:42:47 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|