A. Плюс один на подмножестве
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп получил в подарок массив целых чисел $$$a[1 \dots n]$$$. Он хочет произвести некоторое количество операций (возможно, ноль), чтобы все элементы массива стали одинаковыми (то есть, чтобы стало $$$a_1=a_2=\dots=a_n$$$).

  • За одну операцию он может взять какие-то индексы в массиве и увеличить числа под этими индексами на $$$1$$$.

Например, пусть $$$a=[4,2,1,6,2]$$$. Он может произвести следующую операцию: выбрать индексы 1, 2 и 4 и увеличить их всех на $$$1$$$. В итоге за одну операцию он может получить новое состояние массива $$$a=[5,3,1,7,2]$$$.

За какое минимальное количество операций он может сделать так, что все элементы массива стали равны между собой (то есть, чтобы стало $$$a_1=a_2=\dots=a_n$$$)?

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

Первая строка входных данных содержит единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.

Далее следуют описания наборов входных данных.

Первая строка описания каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 50$$$) — длину массива $$$a$$$.

Вторая строка описания каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — элементы массива $$$a$$$.

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

Для каждого набора входных данных выведите одно целое число — минимальное необходимое количество операций, чтобы сделать все элементы массива $$$a$$$ одинаковыми.

Пример
Входные данные
3
6
3 4 2 4 1 2
3
1000 1002 998
2
12 11
Выходные данные
3
4
1
Примечание

Первый набор входных данных:

  • $$$a=[3,4,2,4,1,2]$$$ берём $$$a_3, a_5$$$ и проводим на них операцию плюс один, в итоге получаем $$$a=[3,4,3,4,2,2]$$$.
  • $$$a=[3,4,3,4,2,2]$$$ берём $$$a_1, a_5, a_6$$$ и проводим на них операцию плюс один, в итоге получаем $$$a=[4,4,3,4,3,3]$$$.
  • $$$a=[4,4,3,4,3,3]$$$ берём $$$a_3, a_5, a_6$$$ и проводим на них операцию плюс один, в итоге получаем $$$a=[4,4,4,4,4,4]$$$.

Существуют и другие последовательности из $$$3$$$ операций, после применения которых все элементы станут равны.

Второй набор входных данных:

  • $$$a=[1000,1002,998]$$$ 2 раза берём $$$a_1, a_3$$$ и проводим на них операцию плюс один, в итоге получаем $$$a=[1002,1002,1000]$$$.
  • $$$a=[1002,1002,1000]$$$ также 2 раза берём $$$a_3$$$ и проводим на нём операцию плюс один, в итоге получаем $$$a=[1002,1002,1002]$$$.

Третий набор входных данных:

  • $$$a=[12,11]$$$ берём $$$a_2$$$ и проводим на нём операцию плюс один, в итоге получаем $$$a=[12,12]$$$.