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,unroll-all-loops")
#pragma GCC optimize("O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
//#pragma GCC target("popcnt")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long double ld;

#define sz(a) (ll)((a).size())
#define fixed cout << setprecision(25) << fixed;
#define all(v) (v).begin(), (v).end()
#define rall(v) v.rbegin(), v.rend()
#define debug(x) cerr << #x << " = " << x << endl;
#define debug2(x, y) cerr << #x << " = " << x <<", "<< #y << " = " << y << endl;
#define debug3(x, y, z) cerr << #x << " = " << x << ", "<< #y << " = " << y << ", "<< #z << " = " << z << endl;
#define debug4(x, y, z, u) cerr << #x << " = " << x << ", "<< #y << " = " << y << ", "<< #z << " = " << z << ", "<< #u << " = " << u << endl;
#define debug_a(x) cerr << #x << endl; for (auto e : (x)) cerr << e << ' '; cerr << endl;
#define debug_b(x) cerr << #x << endl; for (auto e : (x)) cerr << " ( " << e.st << ' ' << e.nd << " ) "; cerr << endl;
#define debug_c(x) cerr << #x << endl; for (auto e : (x)) cerr << " ( " << e[0] << ' ' << e[1] << ' ' << e[2] << " ) "; cerr << endl;
#define pikachu push_back
#define mp make_pair
#define st first
#define nd second
#define i128 __int128
#define pt(s) (s)[sz((s)) - 2]
#define pll pair<ll, ll>

const ll INF = (is_same<int, ll>::value ? 1e9 + 666 : 1e18l + 666);
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

template<class t1, class t2>
inline bool cmin(t1 &a, const t2 &b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class t1, class t2>
inline bool cmax(t1 &a, const t2 &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

inline ll bpow(ll a, ll b, ll mod) {
    ll res = 1;
    for (; b; b >>= 1) {
        if (b & 1) {
            res *= a;
            res %= mod;
        }
        a *= a;
        a %= mod;
    }
    return res;
}

#ifndef LOCAL
void UseFiles(const string &s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}
#else

void UseFiles(const string &) {}

#endif

void run();


signed main() {
    iostream::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    run();
}

void task() {
    ll n, sm = 0, x;
    cin >> n;
    for (ll i = 0; i < n; i++) cin >> x, sm += x;
    cout << (n - (sm % n)) * (sm % n) << '\n';
}

void run() {
    ll t;
    cin >> t;
    while (t-- > 0) {
        task();
    }
}