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.*;
 import java.lang.*;
 import java.io.*;
 
 /* Name of the class has to be "Main" only if the class is public. */
 public class B_Customising_the_Track
 {
     static int M = 1_000_000_007;
     static final PrintWriter out =new PrintWriter(System.out);
     static final FastReader fs = new FastReader();
     public static void main (String[] args) throws java.lang.Exception
     {
           
           int t= fs.nextInt();
           for(int i=0;i<t;i++)
           {
               long n=fs.nextLong();
               long sum=0;
               for(long j=0;j<n;j++){
                   long gg=fs.nextLong();
                   sum=sum+gg;
               }
               if(sum%n==0){
                   out.println(0);
               }else{
                   out.println((sum-(sum/n)*n)*(n-(sum-(sum/n)*n)));
               }
           }
           out.flush();
  }
         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;
         }
 int [] arrayIn(int n) throws IOException
     {
         int  arr[] = new int[n];
         for(int i=0; i<n; i++)
         {
             arr[i] = nextInt();
         }
         return arr;
     }
     }
     
     public static class Pairs implements Comparable<Pairs>
     {
         int value,index;
         Pairs(int value, int index)
         {
             this.value = value;
             this.index = index;
         }
         public int compareTo(Pairs p)
         {
             return Integer.compare(this.value, p.value);
         }
     }
     static final Random random = new Random();
  
     static void ruffleSort(int arr[])
     {
         int n = arr.length;
         for(int i=0; i<n; i++)
         {
             int j = random.nextInt(n),temp = arr[j];
             arr[j] = arr[i];
             arr[i] = temp;
         }
         Arrays.sort(arr);
     }
     static long nCk(int n, int k) {
         return (modMult(fact(n),fastexp(modMult(fact(n-k),fact(k)),M-2)));
     }
  
     static long fact (long n) {
  
         long fact =1;
         for(int i=1; i<=n; i++) {
             fact = modMult(fact,i);
         }
         return fact%M;
     }
  
     static long modMult(long a,long b) {
         return a*b%M;
     }
  
     static long fastexp(long x, int y){
         if(y==1) return x;
  
         long ans = fastexp(x,y/2);
         if(y%2 == 0) return modMult(ans,ans);
         else return modMult(ans,modMult(ans,x));
     }
 }