B. Друзья и конфеты
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Поликарпа есть $$$n$$$ друзей, у $$$i$$$-го из которых есть $$$a_i$$$ конфет. Друзьям Поликарпа не нравится, когда у них различается количество конфет. Иными словами, они хотят, чтобы все $$$a_i$$$ были равны. Чтобы добиться этого, Поликарп делает следующее ровно один раз:

  • Поликарп выбирает $$$k$$$ ($$$0 \le k \le n$$$) произвольных друзей (пусть он выбрал друзей с номерами $$$i_1, i_2, \ldots, i_k$$$);
  • Поликарп перераспределяет их конфеты среди всех $$$n$$$ друзей, всего таких конфет $$$a_{i_1} + a_{i_2} + \ldots + a_{i_k}$$$. При перераспределении для каждой конфеты из $$$a_{i_1} + a_{i_2} + \ldots + a_{i_k}$$$ он выбирает нового владельца (любого из $$$n$$$ друзей, конфета может вновь достаться старому владельцу).

Заметьте, что число $$$k$$$ заранее не фиксировано и может быть произвольным. Ваша задача — найти минимальное возможное значение $$$k$$$.

Например, если $$$n=4$$$ и $$$a=[4, 5, 2, 5]$$$, тогда Поликарп мог сделать следующее:

  • Поликарп выбирает $$$k=2$$$ друзей с номерами $$$i=[2, 4]$$$ и перераспределяет $$$a_2 + a_4 = 10$$$ конфет так, что в итоге $$$a=[4, 4, 4, 4]$$$ (две конфеты достаются человеку под номером $$$3$$$).

Заметьте, что в данном примере Поликарп не может выбрать $$$k=1$$$ друга так, чтобы можно было перераспределить конфеты так, что в итоге все $$$a_i$$$ равны между собой.

Для данных $$$n$$$ и $$$a$$$ определите минимальное значение $$$k$$$. При этом значении $$$k$$$ Поликарп должен иметь возможность выбрать $$$k$$$ друзей и перераспределить их конфеты так, что у всех в итоге будет одинаковое количество конфет.

Входные данные

В первой строке содержится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$). Далее следуют $$$t$$$ наборов входных данных.

В первой строке каждого набора входных данных содержится одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^4$$$).

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите:

  • минимальное значение $$$k$$$ при котором Поликарп может выбрать ровно $$$k$$$ друзей так, чтобы можно было перераспределить конфеты искомым образом;
  • «-1», если такого значения $$$k$$$ не существует.
Пример
Входные данные
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
Выходные данные
2
1
-1
0
0