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 n sub-tracks. You are given an array a where a_i represents the number of traffic cars in the i-th sub-track. You define the inconvenience of the track as ∑_{i=1}^{n} ∑_{j=i+1}^{n} \lvert a_i-a_j\rvert, where |x| is the absolute value of x. 

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 t (1≤ t≤ 10 000) — the number of test cases.

The first line of each test case contains a single integer n (1≤ n≤ 2⋅ 10^5).

The second line of each test case contains n integers a_1, a_2, …, a_n (0≤ a_i≤ 10^9).

It is guaranteed that the sum of n over all test cases does not exceed 2⋅ 10^5.

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


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


Output


0
4
21

Note

For the first test case, you can move a car from the 3-rd sub-track to the 1-st sub-track to obtain 0 inconvenience.

For the second test case, moving any car won't decrease the inconvenience of the track.
#include<bits/stdc++.h>
#include<cstdio>
#include <iomanip> 
typedef long long int lli;
using namespace std;
lli binpow(lli a, lli b) {
    if (b == 0)
        return 1;
    lli res = binpow(a, b / 2);
    if (b % 2)
        return res * res * a;
    else
        return res * res;
}
long long binpowMOD(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}
int gcd(int a, int b)
{
    if (a == 0)
        return b;
    return gcd(b % a, a);
}
void sol(){
    map<lli,lli> mp;
    int n;
    cin>>n;
    int a[n];
    lli sum=0;
    for(int i=0;i<n;i++){cin>>a[i];sum+=a[i];}
    lli b[n];
    for(int i=0;i<n;i++){
        b[i] = sum/n;
    }
    lli rem = sum%n;
    lli c = 0;
    int i=0;
    while(c<rem&&i<n){
        b[i]++;
        i++;
        c++;
    }
    for(int i=0;i<n;i++){
        mp[b[i]]++;
    }
    if(mp.size()==1){cout<<0<<"\n";return ;}
    lli ans=0;
    vector<lli> arr;
    for(auto it = mp.begin();it!=mp.end();it++){
        arr.push_back(it->first);
    }
    sort(arr.begin(),arr.end(),greater<int>());
    for(int i=0;i<arr.size()-1;i++){
        for(int j=i+1;j<arr.size();j++){
            lli a = (abs(arr[i]-arr[j]))*(mp[arr[i]]*mp[arr[j]]);
            ans+=a;
        }
    }
    cout<<ans<<"\n";
}   


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        sol();
    }
    //sol();
}