/**
    BISMILLAH
    @Author: Arham
*/

// #include <bits/stdc++.h>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<stack>
#include<list>
#include<iostream>
#include<fstream>
#include<numeric>
#include<string>
#include<vector>
#include<cstring>
#include<map>
#include<iterator>
#include<iomanip>
#include<time.h>
#include<utility>
using namespace std;
#define Go ios::sync_with_stdio(0);cin.tie(0);
#define pi acos(-1)
#define PI 3.141592653589793238462
#define set_bits __builtin_popcountll
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
using ll = long long;
#define endl '\n'
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
#define ff first
#define ss second
#define debugT(x) cerr << #x << '>' << x << endl
#define dbg(x) cout << #x << '>' << x << endl
#define lg(val) log2(val)
#define cerr cout

// typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;
// typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update > pbds; // find_by_order, order_of_key

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x << " "; print(x); cerr << endl;
#else
#define debug(x)
#endif

void print(ll nw) {cerr << nw;}
void print(int nw) {cerr << nw;}
void print(string nw) {cerr << nw;}
void print(char nw) {cerr << nw;}
void print(lld nw) {cerr << nw;}
void print(double nw) {cerr << nw;}
void print(ull nw) {cerr << nw;}

template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.f); cerr << ","; print(p.s); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}

const ll mod = 1e9+7;
template<typename T>
T pwTwo(T val) {
    return (T)1<<val;
}

// For prefix sum:
// partial_sum(v.begin(), v.end(), v.begin());

#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))

#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) {
    cout << *it << " = " << a << endl;
    err(++it, args...);
}

struct CP {
    CP() {}
    void solN(int id) { // DUMMY_ARGUMENT?
        int n;
        cin >> n;
        vi v(n);
        ll sum = 0;
        rep (i, 0, n) cin >> v[i], sum += v[i];
        int av = sum/n;
        ll cur = 0;
        for (int i = 0; i < n; i++) {
            v[i] = av;
        }
        int rs = sum - av*n;
        for (int i = 0; i < n; i++) {
            if (!rs) break;
            v[i]++;
            rs--;
        }
        // int ind = n;
        // for (int i = 0; i < n; i++) {
        //     if (cur + av <= sum) {
        //         cur += av;
        //         v[i] = av;
        //     } else {
        //         v[i] = sum - cur;
        //         ind = i+1;
        //         break;
        //     }
        // }
        // for (int i = ind; i < n; i++) {
        //     v[i] = 0;
        // }
        // ind--;
        // for (int i = 0; i < n; i++) {
        //     if (v[ind] == av) break;
        //     v[ind]++;
        //     v[i]--;
        // }
        sort(v.rbegin(), v.rend());
        vl pre(n);
        sum = 0;
        for (int i = 0; i < n; i++) {
            sum += v[i];
            pre[i] = sum;
        }
        ll mn = 0;
        for (int i = 0; i < n; i++) {
            ll nw = n-i-1;
            mn += nw*v[i];
            mn -= pre[n-1]-pre[i];
        } cout << mn << endl;
    }
};

// class CP {
// public:
//     CP() {}
//     void solN(int id) { // DUMMY_ARGUMENT?
        
//     }
// };

void Local() {
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r+", stdin);
    freopen("out.txt", "w+", stdout);
    // freopen("Error.txt", "w", stderr);
    #endif
}

int main() {
    // Local();
    Go

    int t = 1, id = 1;
    // scanf("%d", &t);
    cin >> t;
    // cin >> ws;

    CP think;
    --t;

    do {
        think.solN(id++);
    } while(t--);

    return 0;
}