B. Customising the Track

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Highway 201 is the most busy street in Rockport. Traffic cars cause a lot of hindrances to races, especially when there are a lot of them. The track which passes through this highway can be divided into nn sub-tracks. You are given an array aa where aiai represents the number of traffic cars in the ii-th sub-track. You define the inconvenience of the track as ∑i=1n∑j=i+1n|ai−aj|∑i=1n∑j=i+1n|ai−aj|, where |x||x| is the absolute value of xx.

You can perform the following operation any (possibly zero) number of times: choose a traffic car and move it from its current sub-track to any other sub-track.

Find the minimum inconvenience you can achieve.

Input

The first line of input contains a single integer tt (1≤t≤100001≤t≤10000) — the number of test cases.

The first line of each test case contains a single integer nn (1≤n≤2⋅1051≤n≤2⋅105).

The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (0≤ai≤1090≤ai≤109).

It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052⋅105.

Output

For each test case, print a single line containing a single integer: the minimum inconvenience you can achieve by applying the given operation any (possibly zero) number of times.

Example

input

Copy

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

output

Copy

0
4
21

Note

For the first test case, you can move a car from the 33-rd sub-track to the 11-st sub-track to obtain 00 inconvenience.

For the second test case, moving any car won't decrease the inconvenience of the track.

             本题主要是要理解最小不便怎么求，我英文水平不太好，就不翻译了，说说我对这题的理解，最小不便就是（每条道路的车辆和其他道路车辆的绝对差）的和（下面的计算用s代替），既然是差的话，我就是想怎么把他降到最小，那就是平均值了，把每条道路的车辆都相加，再除以道路条数就是平均值，这样就变成了每条道路的车辆都相同了，当然会有余数，下面就处理余数。

              要最小就把这个余数分成若干1，分别加到每条道路中（因为时除余道路，所以这个余数一定小于道路数（道路数下面计算用n代替）），这样就变成了有些道路是平均值，有些是平均值加1，，平均值加1的道路条数可以用 s%n ，然后就是车辆时平均数的道路可以是 n-s%n。

              所以每一条平均值加1的道路的不便就是 n-s%n，一共有s%n条，所以不便和为 (s%n)*(n-s%n)。

              下面附上AC代码，写的不好还请多见谅：

#include <iostream>
using namespace std;
typedef long long ll;

int main()
{
    int t,i,n;
    ll s,c,a;//s计算所以的车辆，c计算移动次数，会超过int型
    cin>>t;
    while(t--){
        cin>>n;
        s=0;//车辆每次初始为0
        for(i=0;i<n;i++){
            cin>>a;//每条路的车辆数
            s+=a;
        }
        c=(s%n)*(n-s%n);//计算最小不便
        cout<<c<<endl;
    }
}