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 TT {

    static Uzi uzi;
    static int counter = 0;
    static long[] dp;

    public static void main(String[] args) throws IOException {
        FastReader fk = new FastReader();
//        Scanner fk = new Scanner(System.in);
        PrintWriter pr = new PrintWriter(System.out);
        //FileWriter wr = new FileWriter("output.txt");
        uzi = new Uzi();

        int mod = 5;
        int t = fk.nextInt();

        while(t-- > 0){
            int n = fk.nextInt();
            long sum =0;

            for(int i =0; i<n; i++)
                sum += fk.nextLong();

            long d = sum%n;
            pr.println(d * (n-d));

        }
        pr.close();


    }
}


class Uzi {
    boolean[] primes;
    int N;
    long[] fact;

    public Uzi(){}

    public Uzi(int n) {
        this.N = n;
        this.primes = new boolean[N + 1];
        this.fact = new long[N+1];
    }

    public int fast_exponentiation(int n, int b, int mod){
        // Time complexity: O(logn), Space complexity: O(1)
        int res = 1;
        while(b > 0){
            res = (res * (b%2 == 1? n : 1)) % mod;
            n = (n*n) % mod;
            b >>= 1;
        }

        return res;

    }

    public void fact(){
        fact[0] = 1;

        for(int i =1; i<= N; i++){
            fact[i] = i*fact[i-1];
        }
    }

    public long gcd(long a, long b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    public void seive() {
        Arrays.fill(primes, true);
        primes[0] = primes[1] = false;

        for (int i = 2; i * i <= N; i++) {
            if (primes[i]) {
                for (int j = i * i; j <= N; j += i)
                    primes[j] = false;
            }
        }
    }

    public int countDivisors(long num) {
        int counter = 0;

        for (int i = 1; i < Math.sqrt(num); i++) {
            if (num % i == 0)
                counter += (i * i == num) ? 1 : 2;
        }
        return counter;
    }

    public boolean binary_search(int[] arr, long key) {
        int s = 0, e = arr.length - 1, curr;

        while (s <= e) {
            curr = (s + e) / 2;
            if (arr[curr] == key)
                return true;
            else {
                if (arr[curr] > key)
                    e = curr - 1;
                else
                    s = curr + 1;
            }
        }

        return false;
    }

    private int elementJustGreater(int[] arr, int k) {
        // to find the first arr[i] >= k using binary search

        int s = 0, e = arr.length - 1, curr;
        int ans = -1;

        while (s <= e) {
            curr = (s + e) / 2;
            if (arr[curr] >= k) {
                ans = arr[curr];
                e = curr - 1;
            } else
                s = curr + 1;
        }

        return ans;
    }

    public int[] elementJustSmaller(int[] arr, long k) {
        // to find the first arr[i] <= k using binary search
        int s = 0, e = arr.length - 1, curr;
        int[] ans = {-1, 0};

        while (s <= e) {
            curr = (s + e) / 2;
            if (arr[curr] <= k) {               // should be less than or equal to
                //ans = arr[curr];
                if(arr[curr] == k)
                    ans = new int[]{curr, 0};
                else
                    ans = new int[]{curr, 1};
                s = curr + 1;
            } else
                e = curr - 1;
        }
        return ans;
    }

    private void fxn(int[] arr, int n) {
        Stack<Integer> stack = new Stack<>();
        int[] output = new int[n];
        int index, curr;

        for (int i = 0; i < n; i++) {
            curr = arr[i];
            while (!stack.isEmpty() && arr[stack.peek()] <= curr) {
                index = stack.pop();
                output[index] = curr;
            }

            stack.push(i);
        }

        while (!stack.isEmpty()) {
            index = stack.pop();
            output[index] = -1;
        }

        System.out.println(Arrays.toString(output));
    }
}

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;
    }
}



