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>
#define ll long long
using namespace std;
const int MOD = 1000000007;

//-----------INLINE FUNC---------
inline int gcd(int a, int b) {return b ? gcd(b, a % b) : a; }
inline int lcm(int a, int b) {return a * b / gcd(a, b); }
inline int add(int a, int b) {return ((a % MOD) + (b % MOD)) % MOD;}
inline int multi(int a, int b) {return ((a % MOD) * (b % MOD)) % MOD;}
inline int sub(int a, int b) 
{ a %= MOD; b %= MOD; a -= b; if (a < 0) a += MOD; return a;}

bool isPrime(int  x)
{   
	if (x <= 4 || x % 2 == 0 || x % 3 == 0) return x == 2 || x == 3; 
	for (int i = 5; i * i <= x; i += 6)
	{
		if (x % i == 0 || x % (i + 2) == 0) { return 0;}
	}
	return 1;
}
 
ll prime[1000002];
 
int Prime(int a)// FOR SINGLE TO KNOW FOR PRIME
{
    for(int i=2;i<=a/2;++i)
    {
        if(a%i==0)
        {
            return 0;
        }
    }
    return 1;
}
 
void sieve()// FOR PRIMES TILL A VALUE
{   for(int i=0;i<=1000001;i++)
    prime[i]=0;
    int maxn=1000001;
    for(int i=2;i<=maxn;i++)
    {
        if(prime[i]==0)
        {
            for(int j=i;j<=maxn;j+=i)
            {
                prime[j]++;
            }
        }
    }
}
 int ceilIndex(vector<int> a, int l, int h, int find)
    {
        
        while(l<h)
        {
            int m=(l+h)/2;
            if(a[m]>=find) h=m;
            else l=m+1;
        }
        return h;        
    }
   
    
    void run_fun()
    {
       long long  int n;cin>>n;
       long long int s=0,in;
        for(long long int i=0;i<n;i++)
        {
         cin>>in;
         s+=in;
        }
        long long int fir=s%n;
        long long int sec=(n-s%n);
        cout<<fir*(sec)<<endl;
     
    }
    int main() 
    {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t; cin>>t;
    while(t--) run_fun();
    return 0;
    
    }
