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

Вас попросили присмотреть за вашим племянником, который любит играть с кубиками необычным способом.

У него есть $$$n$$$ коробок и в $$$i$$$-й коробке лежит $$$a_i$$$ кубиков. Его игра состоит из двух ходов:

  1. он выбирает произвольную коробку $$$i$$$;
  2. он пытается переложить все кубики из $$$i$$$-й коробки в другие коробки.
Если у него получится сделать равное количество кубиков в каждой из оставшихся $$$n - 1$$$ коробок, то он обрадуется, а если не получится — расстроится. Заметьте, что ваш племянник может перекладывать кубики только из выбранной коробки; он не может перекладывать кубики из других коробок.

Вы не хотите, чтобы ваш племянник расстраивался, поэтому вы решили доложить несколько дополнительных кубиков в некоторые коробки так, что независимо от того, какую коробку $$$i$$$ он выберет, он не расстроится. Какое минимальное количество кубиков вам нужно доложить?

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

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

Во второй строке каждого набора заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — количество кубиков в каждой коробке.

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

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

Для каждого набора входных данных, выведите одно целое число — минимальное количество кубиков, которое вам нужно доложить. Можно доказать, что ответ всегда существует, то есть количество кубиков конечное.

Пример
Входные данные
3
3
3 2 2
4
2 2 3 2
3
0 3 0
Выходные данные
1
0
3
Примечание

В первом наборе входных данных, вы можете, например, положить один дополнительный блок в первую коробку и сделать $$$a = [4, 2, 2]$$$. Если ваш племянник выберет коробку с $$$4$$$ кубиками, то он переложит два кубика во вторую коробку и два кубика в третью. Если же он выберет коробку с $$$2$$$ кубиками, то оно переложит эти два кубика в другую коробку с $$$2$$$ кубиками.

Во втором наборе, вам не нужно докладывать кубики, потому что независимо от того, какую коробку он выберет, он всегда сможет выровнять количество кубиков в других коробках.

В третьем наборе, вам нужно доложить хотя бы $$$3$$$ кубика. Например, вы можете положить $$$2$$$ кубика в первую коробку и $$$1$$$ кубик в третью. Вы получите $$$a = [2, 3, 1]$$$.