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 <iostream>
#include <algorithm>
#include <string.h>
#include <cmath>
#include <cstring>
#include <bits/stdc++.h>

#define endl "\n"
#define sss(a) scanf("%d",&a)
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define int ll
#define ull unsigned long long
#define sd(a) scanf("%d",&a)
#define  sldd(a, b) scanf("%lld %lld", &a,&b)
#define  sld(a) scanf("%lld",&a)
#define pld(d) printf("%lld\n",d)
#define itn int
#define log(a, b) log(a)/log(b)
#define hh endl
#define ppp(a) printf("%lld\n",a)
#define cf cin >> t;while(t--){solve;}
#define pii pair<int,int>
#define sssc(a) scanf("%c",&a)
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define mm(a, b) memset(a,b,sizeof(a))
#define debug cout << "debug" << endl;
using namespace std;

// 内联函数要先声明
inline int max(int a, int b);

inline int min(int a, int b);

int max(int a, int b) {
    return (a > b ? a : b);
}

int min(int a, int b) {
    return (a < b ? a : b);
}

//快速幂
int kuai(int a, int b) {
    int ans = 1;
    while (b) {
        if (b & 1) {
            ans = ans * a;
        }
        a = a * a;
        b = b / 2;
    }
    return ans;
}

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

/*
 * *********************************************************************************************************************
 */
int n;
int a, b;
const int maxn = 2e5 + 10;
int arr[maxn];

void slove() {
    cin >> n;
    int sum = 0;
    for (itn i = 1; i <= n; i++) {
        int x;
        cin >> x;
        sum += x;
    }
    int num = sum % n;
    int ans = num * (n - num);
    cout << ans << endl;
}

signed main() {
    int t;
    cin >> t;
    while (t--) {
        slove();
    }
    return 0;
}