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

Исследуя джунгли, вы наткнулись на редкого орангутана с галстуком-бабочкой! Вы пожали орангутану руку и предложили ему немного еды и воды. В ответ...

Орангутан подарил вам массив $$$a$$$ длины $$$n$$$. Используя $$$a$$$, вы построили два массива $$$b$$$ и $$$c$$$, каждый из которых будет содержать $$$n$$$ элементов, следующим образом:

  • $$$b_i = \min(a_1, a_2, \ldots, a_i)$$$ для каждого $$$1 \leq i \leq n$$$.
  • $$$c_i = \max(a_1, a_2, \ldots, a_i)$$$ для каждого $$$1 \leq i \leq n$$$.

Определим счёт массива $$$a$$$ как $$$\sum_{i=1}^n c_i - b_i$$$ (т.е. сумму $$$c_i - b_i$$$ по всем $$$1 \leq i \leq n$$$). Прежде чем вычислять счёт, вы можете переставить элементы $$$a$$$ в любом порядке.

Найдите максимальный счёт, который вы можете получить, если оптимально переставите элементы $$$a$$$.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

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

Следующая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 1000$$$) — элементы массива $$$a$$$.

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

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

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

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

В первом наборе входных данных нет другого способа переставить элементы $$$a$$$. Таким образом, $$$b = [69]$$$ и $$$c = [69]$$$. Единственный возможный счёт — $$$69 - 69 = 0$$$.

Во втором наборе входных данных можно переставить элементы $$$a$$$ так: $$$[7, 5, 6]$$$. Тогда $$$b = [7, 5, 5]$$$ и $$$c = [7, 7, 7]$$$. Счёт в этом случае будет равен $$$(7 - 7) + (7 - 5) + (7 - 5) = 4$$$. Можно показать, что это максимально возможный счёт.