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>
using namespace std;

// ascii value of ('0'-'9') is(48 - 57) and (a-z) is (97-122) and (A-Z) is(65-90) and 32 for space

#define endl "\n"
#define int long long

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << endl;
    err(++it, args...);
}

// use error(args..)

const int INF = (int)2e9  + 10;
const int32_t MOD=1e9+7;
const int32_t MM=998244353;
const int N=200200;


void solve()
{

    int n;
    cin>>n;

    vector <int> v(n);

    int sum  =0;

    for(int i=0; i<n; i++)
    {
        cin>>v[i];
        sum += v[i];
    }

    //int foreach = sum/n;

    int ans = n - sum%n;

    int res = sum%n;
    res *= ans;
    cout<<res<<endl;

}

signed main() {

    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("inp.txt", "r", stdin);
    freopen("newop.txt", "w", stdout);
    #endif

    int t = 1;

    cin>>t;

    while(t--)
    {
        solve();
    }

    return 0;
}