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

Саша нашел массив $$$a$$$, состоящий из $$$n$$$ целых чисел, и попросил вас раскрасить элементы.

Вы должны раскрасить каждый элемент массива. Вы можете использовать столько цветов, сколько захотите, но каждый элемент должен быть окрашен ровно в один цвет, и для каждого цвета должен быть хотя бы один элемент этого цвета.

Стоимость одного цвета — это значение $$$\max(S) - \min(S)$$$, где $$$S$$$ — последовательность элементов этого цвета. Стоимость всей раскраски — это сумма стоимостей по всем цветам.

Например, предположим, что у вас есть массив $$$a = [\color{red}{1}, \color{red}{5}, \color{blue}{6}, \color{blue}{3}, \color{red}{4}]$$$, вы раскрасили его элементы в два цвета следующим образом: элементы на позициях $$$1$$$, $$$2$$$ и $$$5$$$ имеют цвет $$$1$$$; элементы на позициях $$$3$$$ и $$$4$$$ имеют цвет $$$2$$$. Тогда:

  • Стоимость цвета $$$1$$$ составляет $$$\max([1, 5, 4]) - \min([1, 5, 4]) = 5 - 1 = 4$$$;
  • Стоимость цвета $$$2$$$ равна $$$\max([6, 3]) - \min([6, 3]) = 6 - 3 = 3$$$;
  • Общая стоимость раскраски равна $$$7$$$.

Для данного массива $$$a$$$ вы должны рассчитать максимальную возможную стоимость раскраски.

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

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

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

Во второй строке каждого набора входных данных дано $$$n$$$ чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 50$$$) — массив $$$a$$$.

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

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

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

В первом примере одной из оптимальных раскрасок является $$$[\color{red}{1}, \color{red}{5}, \color{blue}{6}, \color{blue}{3}, \color{red}{4}]$$$. Ответ для неё равен $$$(5 - 1) + (6 - 3) = 7$$$.

Во втором примере единственной возможной раскраской является $$$[\color{blue}{5}]$$$, для которой ответ равен $$$5 - 5 = 0$$$.

В третьем примере оптимальной окраской является $$$[\color{blue}{1}, \color{red}{6}, \color{red}{3}, \color{blue}{9}]$$$, для которой ответ равен $$$(9 - 1) + (6 - 3) = 11$$$.