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.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
import java.lang.*;
public class JaiShreeRam{
	static Scanner in=new Scanner();
	static long mod = 1000000007;
	static int seive[]=new int[1000001];
	static int level[]=new int[200001];
	static int parent[][]=new int[200001][18];
	static int count=0;
	static ArrayList<ArrayList<Integer>> al=new ArrayList<>();
	public static void main(String[] args) throws Exception{
		int t=in.readInt();
		while(t-->0) {
			long n=in.readInt();
			long sum=0;
			for(int i=0;i<n;i++) {
				sum+=in.readLong();
			}
			long a=sum%n;
			if(a==0) {
				System.out.println(0);
				continue;
			}
			System.out.println((n-a)*a);
		}
    }
	//static void build()
	static void dfs(int node,int par,int k,int m,int a[]) {
		if(k>m) {
			return;
		}
		int f=1;
		for(int i:al.get(node)) {
			if(i!=par) {
				f=0;
				if(a[i-1]==1) {
					dfs(i,node,k+a[i-1],m,a);
				}
				else {
					dfs(i,node,0,m,a);
				}
			}
		}
		if(al.get(node).size()==1&&f==1) {
			count++;
			return;
		}
	}
	static void seive() {
		Arrays.fill(seive, 1);
		seive[0]=0;
		seive[1]=0;
		for(int i=2;i*i<1000001;i++) {
			if(seive[i]==1) {
				for(int j=i*i;j<1000001;j+=i) {
					if(seive[j]==1) {
						seive[j]=0;
					}
				}
			}
		}
	}
	static int[] nextIntArray(int n){
		int[] arr= new int[n];
		int i=0;
		while(i<n){
			arr[i++]=in.readInt();
		}
		return arr;
	}
	static int[] nextIntArray1(int n){
		int[] arr= new int[n+1];
		int i=1;
		while(i<=n){
			arr[i++]=in.readInt();
		}
		return arr;
	}
	static long gcd(long a, long b) {
		if (b==0) return a;
		return gcd(b, a%b);
	}
 
	static void ruffleSort(long[] a) {
		int n=a.length;
		Random r=new Random();
		for (int i=0; i<a.length; i++) {
			int oi=r.nextInt(n); long temp=a[i];
			a[i]=a[oi];
			a[oi]=temp;
		}
		Arrays.sort(a);
	}
	
	static class Scanner{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String readString() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		double readDouble() {
			return Double.parseDouble(readString());
		}
		int readInt() {
			return Integer.parseInt(readString());
		}
		long readLong() {
			return Long.parseLong(readString());
		}
	}	
}