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.
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define FORD(i, a, b) for (ll i = a ; i > b ; i--)
#define fastio ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define PI 3.14159265
typedef long long ll;
#define vl vector<ll>
#define IN(inp) ll inp;cin>>inp;
#define pb push_back
#define all(a) a.begin(),a.end()
#define FR(i,a) for(auto &i:a)
#define rvl(a,n) vl a;FOR(i,0,n){IN(in); a.pb(in);}
#define test ll t; cin>>t; while(t--)
#define endl "\n"
#define what(A) cout<<#A<<" is "<<A<<endl;
ll MAX = 100000000000000;
ll MOD = 1000000007;
string yes = "YES", no = "NO";
/////////////////////////////////////POWER////////////////////////////////////////

ll power(ll a, ll n, ll mod)
{
    ll res = 1;
    while (n)
    {
        if (n % 2)
        {
            res = (res * a) % mod;
        }
        n /= 2;
        a = (a * a) % mod;
    }
    return res;
}

/////////////////////////////////////SIEVE/////////////////////////////////////////
// vl Prime(100000001);
// vl prime;
// //map<ll, vl>factors;
// void sieve()
// {
//     for (ll i = 2; i <= 10000000; i++)
//     {
//         if (Prime[i] != 0)
//             continue;
//         prime.push_back(i);
//         for (ll j = i * 2; j < 10000001; j += i)
//         {
//             Prime[j] = 1;
//             //factors[j].pb(i);
//         }
//     }
// }


///////////////////////////////////////////////GCD///////////////////////////////////

ll GCD(ll x, ll y)
{
    if (y == 0)
        return x;
    return GCD(y, x % y);
}

///////////////////////////////////////////////DSU//////////////////////////////////

// ll par[400010], siz[400010];
// ll find(ll a)
// {
//     if (par[a] < 0)
//         return a;
//     return par[a] = find(par[a]);
// }
// void union_set(ll a, ll b)
// {
//     a = find(a);
//     b = find(b);
//     if (a != b)
//     {
//         if (siz[a] > siz[b])
//             swap(a, b);
//         siz[b] += siz[a];
//         par[a] = b;
//     }
// }
/////////////////////////////////////////////FENWICK////////////////////////////////
/*
ll FEN[500010];
void update(ll index, ll value,ll siz)
{
    while (index <= siz)
    {
        FEN[index] += value;
        index = index + (index & (-index));
    }
}
ll sum(ll index)
{
    ll ans = 0;
    while (index > 0)
    {
        ans += FEN[index];
        index = index - (index & (-index));
    }
    return ans;
}
*/

void solve()
{
    IN(n);
    rvl(v, n);
    ll s = 0;
    FOR(i, 0, n)
    s += v[i];
    ll ans = (n - (s % n)) * (s % n);
    cout << ans << endl;
}

int main()
{
    fastio
#ifndef ONLINE_JUDGE
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
#endif
    clock_t start, end;
    start = clock();
    // sieve();
    test
    {
        solve();
    }
    end = clock();
    double time_taken = double(end - start) / double(CLOCKS_PER_SEC);
    clog << endl << "Time taken by program is : " << fixed
         << time_taken << setprecision(5);
    clog << " sec " << endl;
    return 0;
};