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 "avl.h"

using namespace std;

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;

// typedef tree<int,null_type,less<int>,rb_tree_tag,
// tree_order_statistics_node_update> ordered_set;
//auto x = s.find_by_order(2);s.order_of_key(6);

#define fatak                         \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);

#define newl cout << "\n";
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define f first
#define s second
#define mid(l, r) (l + (r - l) / 2)

#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define trav(a, x) for (auto &a : x)

// Shortcuts for "common" data types in contests
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vd = vector<double>;
using vs = vector<string>;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
using psi = pair<string, int>;

using vpii = vector<pii>;
using vpll = vector<pll>;
using vpdd = vector<pdd>;
using vpsi = vector<psi>;

using si = set<int>;
using msi = map<string, int>;

// To simplify repetitions/loops, Note: define your loop style and stick with it!
#define loop(i, a, b) \
    for (int i = int(a); i <= int(b); i++) // a to b, and variable i is local!
#define revloop(i, a, b) \
    for (int i = int(a); i >= int(b); i--) // a to b, and variable i is local!
#define TRvi(c, it) \
    for (vi::iterator it = (c).begin(); it != (c).end(); it++)
#define TRvpii(c, it) \
    for (vpii::iterator it = (c).begin(); it != (c).end(); it++)
#define TRmsi(c, it) \
    for (msi::iterator it = (c).begin(); it != (c).end(); it++)
#define INF 1000000000 // 2 billion
// If you need to recall how to use memset:
#define MEMSET_INF 127     // about 2B
#define MEMSET_HALF_INF 63 // about 1B
//memset(dist, MEMSET_INF, sizeof dist); // useful to initialize shortest path distances
//memset(dp_memo, -1, sizeof dp_memo); // useful to initialize DP memoization table
//memset(arr, 0, sizeof arr); // useful to clear array of integers
//priority_queue<int> q;
// priority_queue<int,vector<int>,greater<int>> q;

//binary exponentiation
ll binexp(ll a, ll b)
{
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

bool comp(pii &a, pii &b)
{
    return a.second < b.second;
}
int dist(int d, int a)
{
    int x = a/d;
    return (d*(x+1) - a);
}
void solve()

{
    int n;
    cin >> n;
    vll a(n);
    ll s{};
    loop(i,0,n-1){
        cin >> a[i];
    }
    s = accumulate(all(a),s);
    if(s%n==0)
    {
        cout<<"0\n";
    }
    else{
        ll x = s%n;
        x = x*(n-x);
        cout << x << "\n";
    }


}

int main()
{
    fatak;
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}
