There are n block towers in a row, where tower i has a height of a_i. You're part of a building crew, and you want to make the buildings look as nice as possible. In a single day, you can perform the following operation:

  * Choose two indices i and j (1 ≤ i, j ≤ n; i ≠ j), and move a block from tower i to tower j. This essentially decreases a_i by 1 and increases a_j by 1. 



You think the ugliness of the buildings is the height difference between the tallest and shortest buildings. Formally, the ugliness is defined as max(a)-min(a). 

What's the minimum possible ugliness you can achieve, after any number of days?

Input

The first line contains one integer t (1 ≤ t ≤ 1000) — the number of test cases. Then t cases follow.

The first line of each test case contains one integer n (2 ≤ n ≤ 100) — the number of buildings.

The second line of each test case contains n space separated integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^7) — the heights of the buildings.

Output

For each test case, output a single integer — the minimum possible ugliness of the buildings.

Example

Input


3
3
10 10 10
4
3 2 1 2
5
1 2 3 1 5


Output


0
0
1

Note

In the first test case, the ugliness is already 0.

In the second test case, you should do one operation, with i = 1 and j = 3. The new heights will now be [2, 2, 2, 2], with an ugliness of 0.

In the third test case, you may do three operations: 

  1. with i = 3 and j = 1. The new array will now be [2, 2, 2, 1, 5], 
  2. with i = 5 and j = 4. The new array will now be [2, 2, 2, 2, 4], 
  3. with i = 5 and j = 3. The new array will now be [2, 2, 3, 2, 3]. 

The resulting ugliness is 1. It can be proven that this is the minimum possible ugliness for this test.
// HOPE

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//----------------------------------------------------------------------------------------------------------------------
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//----------------------------------------------------------------------------------------------------------------------
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////                                                                                                       //////////
///////                                                                                                       //////////
///////            RRRRRRRRRRRRR     YY          YY         AA               NN          NN                   //////////
///////            RR         RR      YY        YY        AA  AA             NN NN       NN                   //////////
///////            RR        RR         YY     YY        AA    AA            NN  NN      NN                   //////////
///////            RRRRRRRRRR            YY   YY       AAAAAAAAAAAA          NN    NN    NN                   //////////
///////            RR RR                   YY         AAAAAAAAAAAAAA         NN      NN  NN                   //////////
///////            RR   RR                 YY        AA            AA        NN       NN NN                   //////////
///////            RR     RR               YY       AA              AA       NN          NN                   //////////
///////            RR       RR_____________________________________________________________________________   //////////
////////                                                                                                      //////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//----------------------------------------------------------------------------------------------------------------------
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//----------------------------------------------------------------------------------------------------------------------
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

import com.sun.source.tree.Tree;

import javax.swing.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;
import java.math.*;

public class Codeforces1 {
    static PrintWriter out = new PrintWriter(System.out);
    static final int mod = 1_000_000_007;

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

        int[] readIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        long[] readLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }

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

    //Try seeing general case
    public static void main(String[] args) {
        FastReader s = new FastReader();
        int t = s.nextInt();
        while(t-->0)
        {
            int n = s.nextInt();
            int[] a = s.readIntArray(n);

            long sum = 0;
            for(int x: a)
                sum += x;

            if(sum % n == 0)
                out.println(0);
            else
                out.println(1);
        }


        out.close();
    }

    public static void find()
    {

    }




































































    /////////////////////////////////////////////////THE END///////////////////////////////////////////////////////////
    //////////////////////////////////////////////////////////////////////////////////////////////////////////////////

    public static int gcd(int x,int y)
    {
        return y==0?x:gcd(y,x%y);
    }
    public static long gcd(long x,long y)
    {
        return y==0L?x:gcd(y,x%y);
    }

    public static int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }
    public static long lcm(long a, long b) {
        return (a * b) / gcd(a, b);
    }

    public static long pow(long a,long b)
    {
        if(b==0L)
            return 1L;
        long tmp=1;
        while(b>1L)
        {
            if((b&1L)==1)
                tmp*=a;
            a*=a;
            b>>=1;
        }
        return (tmp*a);
    }

    public static long modPow(long a,long b,long mod)
    {
        if(b==0L)
            return 1L;
        long tmp=1;
        while(b>1L)
        {
            if((b&1L)==1L)
                tmp*=a;

            a*=a;
            a%=mod;
            tmp%=mod;
            b>>=1;
        }
        return (tmp*a)%mod;
    }

    static long mul(long a, long b) {
        return a*b%mod;
    }

    static long fact(int n) {
        long ans=1;
        for (int i=2; i<=n; i++) ans=mul(ans, i);
        return ans;
    }

    static long fastPow(long base, long exp) {
        if (exp==0) return 1;
        long half=fastPow(base, exp/2);
        if (exp%2==0) return mul(half, half);
        return mul(half, mul(half, base));
    }

    static void debug(int ...a)
    {
        for(int x: a)
            out.print(x+" ");
        out.println();
    }

    static void debug(long ...a)
    {
        for(long x: a)
            out.print(x+" ");
        out.println();
    }

    static void debugMatrix(int[][] a)
    {
        for(int[] x:a)
            out.println(Arrays.toString(x));
    }
    static void debugMatrix(long[][] a)
    {
        for(long[] x:a)
            out.println(Arrays.toString(x));
    }

    static void reverseArray(int[] a, int start, int end) {//[start end)
        while(start<end)
        {
            int temp = a[start];
            a[start] = a[end];
            a[end] = temp;
            start++; end--;
        }
    }

    static void reverseArray(long[] a, int start, int end) {
        while(start<end)
        {
            long temp = a[start];
            a[start] = a[end];
            a[end] = temp;
            start++; end--;
        }
    }

    static void sort(int[] a)
    {
        ArrayList<Integer> ls = new ArrayList<>();
        for(int x: a) ls.add(x);
        Collections.sort(ls);
        for(int i=0;i<a.length;i++)
            a[i] = ls.get(i);
    }

    static void sort(long[] a)
    {
        ArrayList<Long> ls = new ArrayList<>();
        for(long x: a) ls.add(x);
        Collections.sort(ls);
        for(int i=0;i<a.length;i++)
            a[i] = ls.get(i);
    }

    static class Pair{
        int x, y;
        Pair(int x, int y)
        {
            this.x = x;
            this.y = y;
        }

        @Override
        public String toString() {
            return "Pair{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }
    static class MyCmp implements Comparator<Pair>
    {
        public int compare(Pair p1, Pair p2)
        {
            return p1.x-p2.x;
        }
    }
}