题目描述

Highway 201 是 Rockport 最繁忙的街道。交通车辆会给比赛带来很多阻碍，尤其是当车辆数量很多时。经过这条高速公路的赛道可以被划分为 $n$ 个子赛道。你会得到一个数组 $a$，其中 $a_i$ 表示第 $i$ 个子赛道上的交通车辆数量。你将赛道的不便度定义为 $\sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} |a_i-a_j|$，其中 $|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$ 个子赛道上的一辆车移动到第 $1$ 个子赛道，从而使不便度变为 $0$。

对于第二个测试用例，无论如何移动车辆，都无法减少赛道的不便度。

由 ChatGPT 4.1 翻译

样例

3
3
1 2 3
4
0 1 1 0
10
8 3 6 11 5 2 1 7 10 4

0
4
21