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.util.Scanner;

public class CustomisingtheTrack {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner s= new Scanner(System.in);
		int t= s.nextInt();
		while(t-->0) {
			int n= s.nextInt();
			double sum =0;
			int a=0;
			for(int i=0;i<n;i++) {
				a= s.nextInt();
				sum+=a;
				sum=sum%n;
			}
			sum=sum%n;
			double zeroes=(n-sum);
			double ones=sum;
			double ans=zeroes*ones;
			String num1=String.valueOf(zeroes);
			num1=num1.substring(0, num1.length()-2);
			
			String num2=String.valueOf(ones);
			num2=num2.substring(0, num2.length()-2);
			mul(num1,num2);
//			String str=String.valueOf(ans);
//			System.out.println(str.substring(0,str.length()-2));
			
		}
	}
	static void mul(String num1,String num2) {
	    {
	       
	        String tempnum1 = num1;

	        String tempnum2 = num2;
	 
	        // Check condition if one string is negative
	        if (num1.charAt(0) == '-'
	            && num2.charAt(0) != '-') {
	            num1 = num1.substring(1);
	        }
	        else if (num1.charAt(0) != '-'
	                 && num2.charAt(0) == '-') {
	            num2 = num2.substring(1);
	        }
	        else if (num1.charAt(0) == '-'
	                 && num2.charAt(0) == '-') {
	            num1 = num1.substring(1);
	            num2 = num2.substring(1);
	        }
	        String s1
	            = new StringBuffer(num1).reverse().toString();
	        String s2
	            = new StringBuffer(num2).reverse().toString();
	 
	        int[] m = new int[s1.length() + s2.length()];
	 
	        // Go from right to left in num1
	        for (int i = 0; i < s1.length(); i++) {
	            // Go from right to left in num2
	            for (int j = 0; j < s2.length(); j++) {
	                m[i + j] = m[i + j]
	                           + (s1.charAt(i) - '0')
	                                 * (s2.charAt(j) - '0');
	            }
	        }
	 
	        String product = new String();
	        // Multiply with current digit of first number
	        // and add result to previously stored product
	        // at current position.
	        for (int i = 0; i < m.length; i++) {
	            int digit = m[i] % 10;
	            int carry = m[i] / 10;
	            if (i + 1 < m.length) {
	                m[i + 1] = m[i + 1] + carry;
	            }
	            product = digit + product;
	        }
	 
	        // ignore '0's from the right
	        while (product.length() > 1
	               && product.charAt(0) == '0') {
	            product = product.substring(1);
	        }
	 
	        // Check condition if one string is negative
	        if (tempnum1.charAt(0) == '-'
	            && tempnum2.charAt(0) != '-') {
	            product = new StringBuffer(product)
	                          .insert(0, '-')
	                          .toString();
	        }
	        else if (tempnum1.charAt(0) != '-'
	                 && tempnum2.charAt(0) == '-') {
	            product = new StringBuffer(product)
	                          .insert(0, '-')
	                          .toString();
	        }
	        else if (tempnum1.charAt(0) == '-'
	                 && tempnum2.charAt(0) == '-') {
	            product = product;
	        }
	        System.out.println(product);
	    }
	}
}