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.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
	
	
	
//    ***                          ++                      
// +=-==+                      +++=-                     
//+-:---==+                   *+=----=                   
//+-:------==+               ++=------==                  
//=-----------=++=========================                
//+--:::::---:-----============-=======+++====             
//+---:..:----::-===============-======+++++++++           
//=---:...---:-===================---===++++++++++         
//+----:...:-=======================--==+++++++++++        
//+-:------====================++===---==++++===+++++      
//+=-----======================+++++==---==+==-::=++**+     
//+=-----================---=======++=========::.:-+*****    
//+==::-====================--:  --:-====++=+===:..-=+*****   
//+=---=====================-...  :=..:-=+++++++++===++*****  
//+=---=====+=++++++++++++++++=-:::::-====+++++++++++++*****+ 
//+=======++++++++++++=+++++++============++++++=======+****** 
//+=====+++++++++++++++++++++++++==++++==++++++=:...  . .+**** 
//++====++++++++++++++++++++++++++++++++++++++++-.     ..-+**** 
//+======++++++++++++++++++++++++++++++++===+====:.    ..:=++++ 
//+===--=====+++++++++++++++++++++++++++=========-::....::-=++* 
//====--==========+++++++==+++===++++===========--:::....:=++*  
//====---===++++=====++++++==+++=======-::--===-:.  ....:-+++   
//==--=--====++++++++==+++++++++++======--::::...::::::-=+++    
//===----===++++++++++++++++++++============--=-==----==+++     
//=--------====++++++++++++++++=====================+++++++     
//=---------=======++++++++====+++=================++++++++     
//-----------========+++++++++++++++=================+++++++    
//=----------==========++++++++++=====================++++++++  
//=====------==============+++++++===================+++==+++++ 
//=======------==========================================++++++

// created by : pritam kumar

    static long LowerBound(long[] a2, long x) { // x is the target value or key
  int l=-1,r=a2.length;
  while(l+1<r) {
    int m=(l+r)>>>1;
    if(a2[m]>=x) r=m;
    else l=m;
  }
  return r;
}
static int UpperBound(int a[], int x) {// x is the key or target value
    int l=-1,r=a.length;
    while(l+1<r) {
       int m=(l+r)>>>1;
       if(a[m]<=x) l=m;
       else r=m;
    }
    return l+1;
 }
    static void ruffleSort(long[] a) {
		int n=a.length;
		Random r=new Random();
		for (int i=0; i<a.length; i++) {
			long oi=r.nextInt(n), temp=a[i];
			a[i]=a[(int)oi];
			a[(int)oi]=temp;
		}
		Arrays.sort(a);
	}
static void ruffleSort(int[] a) {
		int n=a.length;
		Random r=new Random();
		for (int i=0; i<a.length; i++) {
			int oi=r.nextInt(n), temp=a[i];
			a[i]=a[oi];
			a[oi]=temp;
		}
		Arrays.sort(a);
	}
    public static int findIndex(long arr[], long t) 
    { 
 
        // if array is Null 
        if (arr == null) { 
            return -1; 
        } 
 
        // find length of array 
        int len = arr.length; 
        int i = 0; 
 
        // traverse in the array 
        while (i < len) { 
 
            // if the i-th element is t 
            // then return the index 
            if (arr[i] == t) { 
                return i; 
            } 
            else { 
                i = i + 1; 
            } 
        } 
        return -1; 
    }
 
    static long gcd(long a, long b)
    {
        if (a == 0)
            return b; 
        return gcd(b % a, a); 
    }
    static int gcd(int a, int b)
    {
        if (a == 0)
            return b; 
        return gcd(b % a, a); 
    }
 
    // method to return LCM of two numbers
    static long lcm(long a, long b)
    {
        return (a / gcd(a, b)) * b;
    }
 
    public static int[] swap(int a[], int left, int right)
    {
 
        // Swap the data
        int temp = a[left];
        a[left] = a[right];
        a[right] = temp;
 
        // Return the updated array
        return a;
    }
//    public static pair swap(long max0,long max1)
//    {
//    	pair p=new pair(0, 0);
//    	long temp=max0;
//    	max0=max1;
//    	max1=temp;
//    	p.x=max0;
//    	p.y=max1;
//    	return p;
//    	
//    }
    public static void swap(int max0,int max1)
    {
    	int temp=max0;
    	max0=max1;
    	max1=temp;
    }
 
    public static int[] reverse(int a[], int left, int right)
    {
 
        // Reverse the sub-array
        while (left < right) {
            int temp = a[left];
            a[left++] = a[right];
            a[right--] = temp;
        }
 
        // Return the updated array
        return a;
    }
 
  
	static class FastReader {
        BufferedReader br;
        StringTokenizer st;
 
        public FastReader()
        {
            br = new BufferedReader(
                new InputStreamReader(System.in));
        } 
 
        String next()
        {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt() { return Integer.parseInt(next()); }
 
        long nextLong() { return Long.parseLong(next()); }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
 
        String nextLine()
        {
            String str = "";
            try {
                str = br.readLine();
            }
            catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    } 
	static boolean prime[] ;
		static void sieve(int n)
		{
			prime= new boolean[n+1];
	        for (int i = 0; i <= n; i++)
	            prime[i] = true;
	        prime[0]=false;
	        prime[1]=false;
	        for (int p = 2; p * p <= n; p++)
	        {
	            if (prime[p] == true)
	            {
	                for (int i = p * p; i <= n; i += p)
	                    prime[i] = false;
	            }
	        }
	    }
	    static long[][] a;
	    static ArrayList<Integer>[] tree;
	    static long[][] dp;
	    static void bin(int n)
	    {
	        if (n > 1)
	            bin(n / 2);
	        System.out.print(n % 2);
	    }
	public static void main(String[] args) {
		FastReader s=new FastReader();
		int t=s.nextInt();
		while(t-->0)
		{
			long n=s.nextLong();
			long sum=0;
			for(int i=0;i<n;i++)
			{
				long ss=s.nextLong();
				sum+=ss;
			}
			long rr=sum%n;
			System.out.println(rr*(n-rr));
		}
	}
 
	private static boolean isps(int x) {
		if(x>=0)
		{
			long sr=(long)Math.sqrt(x);
			return (sr*sr==x);
		}
		return false;
	}
	private static boolean solver(int[]arr,int n,int sum,boolean[][] mat)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=sum;j++)
            {
                if(arr[i-1]<=j)
                {
                    mat[i][j]=mat[i-1][j-arr[i-1]]||mat[i-1][j];
                }
                else mat[i][j]=mat[i-1][j];
            }
        }
        return mat[n][sum];
    }
	static void dfs(int v, int p){
        dp[0][v] = 0;
        dp[1][v]=0;
 
        for(int u: tree[v])
        {
            if(u!=p) {
 
 
                dfs(u, v);
                dp[0][v] += Math.max(Math.abs(a[0][v] - a[1][u]) + dp[1][u], Math.abs(a[0][v] - a[0][u]) + dp[0][u]);
                dp[1][v] += Math.max(Math.abs(a[1][v] - a[1][u]) + dp[1][u], Math.abs(a[1][v] - a[0][u]) + dp[0][u]);
            }
 
 
        }
    }
}
class pair{
	long x;
	long y;
	public pair(long x,long y)
	{
		this.x=x;
		this.y=y;
	}
}
	
