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.*;
import java.util.*;

public class test3 {
static long MOD = (int)1e9 +7;
static long mod(long n) {
	return (n%MOD +MOD)%MOD;
}
	public static void main(String[] args) throws  IOException {
		FastReader f = new FastReader();
           int t = f.nextInt();
           while(t-->0) {
        	  int n = f.nextInt();
        	  	long sum  =0;
        	  	for(int i =0;i<n;i++) {
        	  		sum+=f.nextInt();
        	  	}
        	  	System.out.println((sum%n*(n-sum%n)));
        	   }
    }

	static long fp(long a, long b) {
	    if (b == 0) return 1;
	    long t = fp(a, b / 2);
	    if (b % 2 == 0) return mod(t * t);
	    else return mod(mod(t * t) * a);
	}
	static long GCD(long a,long b) {
		  if(a%b==0)return b;
		  else return GCD(b,a%b);
	  }
	static ArrayList<Long> primeFectors(long n){
		ArrayList<Long> ret = new ArrayList<>();
		ret.add(1L);
		while (n%2==0)
        {
           ret.add(2L);
            n /= 2;
        }
		for (long i = 3; i <= Math.ceil(Math.sqrt(n)); i+= 2)
        {
			
            // While i divides n, print i and divide n
            while (n%i==0)
            {
                ret.add(i);
                n /= i;
            }
        }
		 if (n > 2)
	            ret.add(n);
		return ret;
	}
	static boolean isPrime(int n)
    {
 
        // Check if number is less than
        // equal to 1
        if (n <= 1)
            return false;
 
        // Check if number is 2
        else if (n == 2)
            return true;
 
        // Check if n is a multiple of 2
        else if (n % 2 == 0)
            return false;
 
        // If not, then just check the odds
        for (int i = 3; i <= Math.sqrt(n); i += 2)
        {
            if (n % i == 0)
                return false;
        }
        return true;
    }
	
	static void print(int x,int y,int d,int n) {
		int i = 0;
		System.out.print(x+" "+y+" ");
			for(int j = x+d;j<y;j+=d) {
				System.out.print(j+" ");
				i++;
			}
			for(int j = x-d;j>0;j-=d) {
				if(i==n)return;
				System.out.print(j+" ");
				i++;
			}
			for(int j = y+d;j<1000000000;j+=d) {
				if(i==n)return;
				System.out.print(j+" ");
				i++;
			}
	}

	static int prime(int n){
	    int ret = 0;
	    while(n%2==0){
	        ret++;
	        n/=2;
	    }
	    for(int i=3;i<=Math.sqrt(n);i+=2){
	        while(n%i==0){
	            ret++;
	            n/=i;
	        }
	    }
	    if(n>2)ret++;
	    return ret;
	}
	static long nCr(int n, int r) 
	{ if(n<r) {
		return 0;
	} 
	    long[] C=new long[r+1]; 
	    C[0] = 1; 
	    for (int i = 1; i <= n; i++) 
	    {  
	        for (int j = Math.min(i, r); j > 0; j--) 
	            C[j] = (C[j] + C[j-1]); 
	    } 
	    return C[r]; 
	}
	

		static ArrayList<Integer> readArray(FastReader f,int size){
			ArrayList<Integer> ret = new ArrayList<Integer>();
			for(int i=0;i<size;i++) {
				ret.add(f.nextInt());
			}return ret;
		}
	 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; 
	        } 
	    }
	 


}










