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.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;

import static java.lang.Math.*;

public class Main
{
	
    static final int mod = (int)1e9+7;
    public static void main(String[] args) throws Exception
    {
        FastReader in = new FastReader();
        PrintWriter out = new PrintWriter(System.out);
        int test =in.nextInt();
        

        while(test-- > 0)      //test
        {  
        	int n=in.nextInt();
        	long a[]=new long[n];
        			long s=0;
        	for(int i=0;i<n;i++)
        	
        		{
        			a[i]=in.nextLong();s+=a[i];
        		}
        	
        	out.println( (n-(s%n))*(s%n) );
        	
        	
        }   //test
        out.flush();
        
    }
   
    
    
    
    public static void rotate(int arr[],int start, int end)
   	{
   	    int t=arr[end];
   	    for(int i=end-1;i>=start;i--)
   	        arr[i+1]=arr[i];
   	        arr[start]=t;
   	}
    
    static int[] intAr(int n)throws IOException
    {
    	FastReader in = new FastReader();
    	int a[]=new int[n];
        for(int i=0;i<n;i++)
        	a[i]=in.nextInt();
    		return a;
    		
    }
    static Long[] longAr(int n)throws IOException
    {
    	FastReader in = new FastReader();
        PrintWriter out = new PrintWriter(System.out);
    	Long a[]=new Long[n];
        for(int i=0;i<n;i++)
        	a[i]=in.nextLong();
    		return a;
    		
    }
    
    public static void reverse(int[] array)           //reverse array
    {
  
        // Length of the array
        int n = array.length;
  
        // Swaping the first half elements with last half
        // elements
        for (int i = 0; i < n / 2; i++) {
  
            // Storing the first half elements temporarily
            int temp = array[i];
  
            // Assigning the first half to the last half
            array[i] = array[n - i - 1];
  
            // Assigning the last half to the first half
            array[n - i - 1] = temp;
        }
    }
    
    static int getMin(int arr[], int n)                             //min element of array 
    {
        return Arrays.stream(arr).min().getAsInt();
    }
 
    static int getMax(int arr[], int n)                               //max element of array 
    {
        return Arrays.stream(arr).max().getAsInt();
    }
   
    static boolean isPrime(int n)                       // check number if prime int
    { 
        // Corner case 
       
        // Check from 2 to n-1 
        for (int i = 2; i <= Math.sqrt(n); i++) 
            if (n % i == 0) 
                return false; 
  
        return true; 
    } 															
    
    static boolean isPrime(long n)                              // check number if prime long
    { 
        
        for (int i = 2; i <= Math.sqrt(n); i++) 
            if (n % i == 0) 
                return false; 
  
        return true; 
    } 															
    
    
    static long gcd(long a, long b)                          // Recursive method to return gcd of a and b

    {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }
     
  
    static long lcm(long a, long b)                               // method to return LCM of two numbers
    {
        return (a / gcd(a, b)) * b;
    }
     
    static boolean isPalindrome(String str)                 //check if string is palindrome
    {
 
        
        int i = 0, j = str.length() - 1;
 
       
        while (i < j) {
 
            
            if (str.charAt(i) != str.charAt(j))
                return false;
 
          
            i++;
            j--;
        }
 
        // Given string is a palindrome
        return true;
    }
    
    
    static int countDigit(long n)           //No. of digits in a number
    {
        int count = 0;
        while (n != 0) {
            n = n / 10;
            ++count;
        }
        return count;
    }
    
    static long numDivisors(long b)             //No. of Divisors in long
    {
    	long ans=0;
    
		for(long i=1;i*i<=b;i++){
			if(b%i==0){
				ans++;
				if(i*i!=b)	ans++;
			}
		}
		return ans;
    }
    
    
    static int numDivisors(int b)             //No. of Divisors in int
    {
    	int ans=0;
		for(long i=1;i*i<=b;i++){
			if(b%i==0){
				ans++;
				if(i*i!=b)	ans++;
			}
		}
		return ans;
    }
    
    static int countOdd(int a[])
    {
    	int n=a.length;
    	int ans=0,i;
    	for(i=0;i<n;i++)
    	{
    		if(a[i]%2==1)
    			ans++;
    	}
    	return ans;
    }
  
    static int maxSubarraySum(int arr[], int n)        //kandane
    {
        int sum=0;
     int max=arr[0];
     for(int i=0;i<n;i++)
     {
         sum+=arr[i];
         if(sum>max)
         max=sum;
         if(sum<0)
         sum=0;
     }
     return max;
     // Your code here
     
    }
    
    
    
    
    
}



class FastReader
{
    BufferedReader br;
    StringTokenizer st;

    public FastReader()
    {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    public String next() throws IOException
    {
        if(st == null || !st.hasMoreElements())
        {
            st = new StringTokenizer(br.readLine());
        }

        return st.nextToken();
    }

    public boolean hasNext() throws IOException
    {
        if(st != null && st.hasMoreElements())
        {
            return true;
        }

        String s = br.readLine();
        if(s == null) {
            return false;
        }

        st = new StringTokenizer(s);

        return st.hasMoreElements();
    }

    public int nextInt() throws IOException
    {
        return Integer.parseInt(next());
    }

    public long nextLong() throws IOException
    {
        return Long.parseLong(next());
    }

    public String nextLine() throws IOException
    {
        return br.readLine();
    }
}