A. Сокращение разрыва
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть $$$n$$$ зданий, состоящих из блоков, и построенных в ряд. Высота $$$i$$$-го здания равна $$$a_i$$$. Вы — глава строительной бригады и хотите, чтобы построенные здания выглядели как можно приятней. За один день вы можете сделать следующую операцию:

  • Выбрать два индекса $$$i$$$ и $$$j$$$ ($$$1 \leq i, j \leq n$$$; $$$i \neq j$$$) и переместить один блок со здания $$$i$$$ на здание $$$j$$$. Фактически, данная операция уменьшает $$$a_i$$$ на $$$1$$$ и увеличивает $$$a_j$$$ на $$$1$$$.

Вы считаете уродливостью зданий разницу между высотой самого высокого и самого низкого зданий. Формально говоря, уродство определяется как $$$\max(a)-\min(a)$$$.

Какого минимально возможного уродства вы сможете достичь, имея в запасе неограниченное количество дней?

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

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

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

Во второй строке каждого набора заданы $$$n$$$ целых чисел через пробел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^7$$$) — высоты зданий.

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

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

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

В первом наборе входных данных, уродство уже равно $$$0$$$.

Во втором наборе, вы можете сделать одну операцию с $$$i = 1$$$ и $$$j = 3$$$. Высоты зданий станут равны $$$[2, 2, 2, 2]$$$ с уродством $$$0$$$.

В третьем наборе, вы можете сделать, например, следующие три операции:

  1. с $$$i = 3$$$ и $$$j = 1$$$: высоты зданий станут равны $$$[2, 2, 2, 1, 5]$$$,
  2. с $$$i = 5$$$ и $$$j = 4$$$: высоты зданий станут равны $$$[2, 2, 2, 2, 4]$$$,
  3. с $$$i = 5$$$ и $$$j = 3$$$: высоты зданий станут равны $$$[2, 2, 3, 2, 3]$$$.
В результате уродство зданий станет равно $$$1$$$. Можно доказать, что это — минимально возможное уродство, достижимое для данного теста.