Description

201号大道是快乐星球最繁忙的公路。快乐星人想在这条路上举办一次赛车比赛，可是交通车辆给比赛造成很大的不便，尤其是当比赛有很多障碍时。这条公路共含有n个子轨道，给定一个数组a，​表示当前在第i个子轨道上的车的数量。‎

你可以执行任意次数（可以为0次）的以下操作：选择任意子轨道上的一辆车，并将其从当前的子轨道移动到任何其他子轨道。

‎定义公路的不便利值为​$\sum^n_{i=1}\sum^n_{j=i+1}|a_i-a_j|$。

找到你可以实现的公路的最小不便利值。

Input Format

第一行输入一个数字​$t(1\le t \le 10000)$,表示测试用例的数量。

每个测试用例的第一行是一个数字​$n(1 \le n \le 2\times 10^5)$。

每个测试用例的第二行包含从​$a_1$到$a_n$​的n个数字​$(0 \le a_i \le 10^9)$。

保证所有测试用例的n的和不超过​$2\times 10^5$。

Output Format

对于每个测试用例，输出单独一行，包含一个数字：经过你任意次（可以为0次）的操作后，可以得到的最小的不便利值。

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

0
4
21​

Hint

对于第一个测试用例，你可以将一辆车从第三个子轨道移动到第一个子轨道上，以此获得的不便利值最小，为0。

对于第二个测试用例，移动哪一辆车都不能减小不便利值。

Source

思维