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

Шоссе 201 — самая оживлённая улица в Рокпорт-Сити. Машины, стоящие в пробках, создают помехи для гонок, особенно когда их много. Гоночная трасса, проходящая через это шоссе, разделена на $$$n$$$ участков. Вам дан массив $$$a$$$, в котором $$$a_i$$$ равно количеству машин, стоящих в пробках на $$$i$$$-м участке. Положим неудобством гоночной трассы значение $$$\sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} \lvert a_i-a_j\rvert$$$, где $$$|x|$$$ — модуль числа $$$x$$$.

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

Найдите минимальное неудобство, которого возможно достичь.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$).

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0\leq a_i\leq 10^9$$$).

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

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

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

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

В первом наборе входных данных вы можете переместить машину с $$$3$$$-го участка на $$$1$$$-й участок, чтобы получить неудобство, равное $$$0$$$.

Во втором наборе перемещение любой машины не уменьшит неудобство гоночной трассы.