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.
import java.util.*;
import java.io.*;
import java.math.*;

public class Main {
    // ArrayList<Integer> al = new ArrayList<>();
    // ArrayList<Pair<Integer, Integer>> al = new ArrayList<>();
    // Set<Integer> set = new TreeSet<>();
    // Pair<Integer, Integer> pair;
    // Map<Integer, Integer> map = new HashMap<>();
    // LinkedList<Integer> ll = new LinkedList<>();
    // for(Map.Entry<Integer,Integer> e:map.entrySet())pn(e.getKey()+"
    // "+e.getValue());
    // map.put(key,map.getOrDefault(key,0)+1);
    // *********************** Code Begins From Here*************************
    static ArrayList<Long> square = new ArrayList<>();

    public static void solve() {
        int n = c.i(), a[] = c.intArray(n), sum = 0;
        for (int e : a)
            sum += e;
        pn((sum % n) / 2);
    }

    public static void main(String[] args) throws FileNotFoundException {
        c = new FastScanner();
        pw = new PrintWriter(System.out);
        int tc = 1;
        tc = c.i();
        long start = System.currentTimeMillis();
        // sieve(10000000);
        // for (long i = 0; i < arr.length; i++) {
        // if (arr[(int) i]) {
        // primes.add(i);
        // }
        // }
        for (long i = 1; i * i <= 1e9; i++)
            square.add(i * i);
        for (int t = 0; t < tc; t++) {
            // p("Case #" + (t + 1) + ": ");
            solve();
        }
        long end = System.currentTimeMillis();
        if (System.getProperty("os.name").equals("Mac OS X")) {
            pn("The Program takes " + (end - start) + "ms");
        }
        pw.close();
    }

    // math util
    private static int countDigits(long l) {
        if (l >= 1000000000000000000L)
            return 19;
        if (l >= 100000000000000000L)
            return 18;
        if (l >= 10000000000000000L)
            return 17;
        if (l >= 1000000000000000L)
            return 16;
        if (l >= 100000000000000L)
            return 15;
        if (l >= 10000000000000L)
            return 14;
        if (l >= 1000000000000L)
            return 13;
        if (l >= 100000000000L)
            return 12;
        if (l >= 10000000000L)
            return 11;
        if (l >= 1000000000L)
            return 10;
        if (l >= 100000000L)
            return 9;
        if (l >= 10000000L)
            return 8;
        if (l >= 1000000L)
            return 7;
        if (l >= 100000L)
            return 6;
        if (l >= 10000L)
            return 5;
        if (l >= 1000L)
            return 4;
        if (l >= 100L)
            return 3;
        if (l >= 10L)
            return 2;
        return 1;
    }

    private static int lower(int a[], int x) {
        int l = 0, r = a.length - 1, mid, ans = -1;
        while (l <= r) {
            mid = l + ((r - l) >> 1);
            if (a[mid] <= x) {
                ans = max(ans, mid);
                l = mid + 1;
            } else
                r = mid - 1;
        }
        return ans;
    }

    private static int upper(int a[], int x) {
        int l = 0, r = a.length - 1, mid, ans = -1;
        while (l <= r) {
            mid = l + ((r - l) >> 1);
            if (a[mid] >= x) {
                ans = mid;
                r = mid - 1;
            } else
                l = mid + 1;
            // pn(l + " " + mid + " " + r);
        }
        return ans;
    }

    private static int cei(double d) {
        return (int) Math.ceil(d);
    }

    private static long ceil(double d) {
        return (long) Math.ceil(d);
    }

    private static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    private static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    private static int abs(int a, int b) {
        return (int) Math.abs(a - b);
    }

    private static int abs(int a) {
        return (int) Math.abs(a);
    }

    private static long abs(long a) {
        return (long) Math.abs(a);
    }

    private static long abs(long a, long b) {
        return (long) Math.abs(a - b);
    }

    private static int max(int a, int b) {
        if (a > b) {
            return a;
        } else {
            return b;
        }
    }

    private static int min(int a, int b) {
        if (a > b) {
            return b;
        } else {
            return a;
        }
    }

    private static long max(long a, long b) {
        if (a > b) {
            return a;
        } else {
            return b;
        }
    }

    private static long min(long a, long b) {
        if (a > b) {
            return b;
        } else {
            return a;
        }
    }

    private static int pow(int base, int exp) {
        int result = 1;
        while (exp != 0) {
            if ((exp & 1) == 1)
                result *= base;
            exp >>= 1;
            base *= base;
        }
        return result;
    }

    private static long powerMod(long base, long exp, long mod) {
        long result = 1;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1) != 0)
                result = (result * base) % mod;
            exp >>= 1;
            base = base * base % mod;
        }
        return result < 0 ? result + mod : result;
    }

    private static long addMod(long a, long b, long mod) {
        return (a % mod + b % mod) % mod;
    }

    private static long subMod(long a, long b, long mod) {
        return (a % mod - b % mod) % mod;
    }

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

    private static long pow(long base, long exp) {
        long result = 1;
        while (exp != 0) {
            if ((exp & 1) == 1)
                result = result * base;
            exp >>= 1;
            base *= base;
        }
        return result;
    }

    // array util
    private static void sortList(ArrayList<Integer> al) {
        Collections.sort(al);
    }

    private static void sortListP(ArrayList<Pair<Integer, Integer>> al) {
        Collections.sort(al);
    }

    private static void sort(int[] a) {
        ArrayList<Integer> al = new ArrayList<>();
        for (int e : a)
            al.add(e);
        sortList(al);
        int i = 0;
        for (int e : al)
            a[i++] = e;
    }

    private static void sort(double[] a) {
        ArrayList<Double> al = new ArrayList<>();
        for (double e : a)
            al.add(e);
        Collections.sort(al);
        int i = 0;
        for (double e : al)
            a[i++] = e;
    }

    private static void sort(char[] a) {
        ArrayList<Character> al = new ArrayList<>();
        for (char e : a)
            al.add(e);
        Collections.sort(al);
        int i = 0;
        for (char e : al)
            a[i++] = e;
    }

    private static void sort(long[] a) {
        ArrayList<Long> al = new ArrayList<>();
        for (long e : a)
            al.add(e);
        Collections.sort(al);
        int i = 0;
        for (long e : al)
            a[i++] = e;
    }

    private static int[] copy(int[] a) {
        int[] ans = new int[a.length];
        for (int i = 0; i < a.length; ++i)
            ans[i] = a[i];
        return ans;
    }

    private static char[] copy(char[] a) {
        char[] ans = new char[a.length];
        for (int i = 0; i < a.length; ++i)
            ans[i] = a[i];
        return ans;
    }

    private static long[] copy(long[] a) {
        long[] ans = new long[a.length];
        for (int i = 0; i < a.length; ++i)
            ans[i] = a[i];
        return ans;
    }
    // output

    private static void pn(Object o) {
        pw.println(o);
    }

    private static void p(Object o) {
        pw.print(o);
    }

    private static void pry() {
        pn("Yes");
    }

    private static void pY() {
        pn("YES");
    }

    private static void prn() {
        pn("No");
    }

    private static void pN() {
        pn("NO");
    }

    private static void flush() {
        pw.flush();
    }

    private static void watch(int[] a) {
        for (int e : a)
            p(e + " ");
        pn("");
    }

    private static void watch(long[] a) {
        for (long e : a)
            p(e + " ");
        pn("");
    }

    private static void watch(char[] a) {
        for (char e : a)
            p(e);
        pn("");
    }

    private static void watchList(ArrayList<Integer> al) {
        for (int e : al)
            p(e + " ");
        pn("");
    }

    private static Set<Integer> putSet(int[] a) {
        Set<Integer> set = new TreeSet<>();
        for (int e : a)
            set.add(e);
        return set;
    }

    private static boolean[] sieve(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        isPrime[0] = false;
        isPrime[1] = false;
        for (int i = 2; i * i <= n; i++) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
        return isPrime;
    }

    static void permute(String s, String answer, ArrayList<Long> al) {
        if (s.length() == 0) {
            al.add(Long.parseLong(answer));
            return;
        }

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            String left_substr = s.substring(0, i);
            String right_substr = s.substring(i + 1);
            String rest = left_substr + right_substr;
            permute(rest, answer + ch, al);
        }
    }

    private static class Pair<U, V> implements Comparable<Pair<U, V>> {
        public final U first;
        public V second;

        public <U, V> Pair<U, V> makePair(U first, V second) {
            return new Pair<U, V>(first, second);
        }

        public Pair(U first, V second) {
            this.first = first;
            this.second = second;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()) {
                return false;
            }

            Pair pair = (Pair) o;

            return !(first != null ? !first.equals(pair.first) : pair.first != null)
                    && !(second != null ? !second.equals(pair.second) : pair.second != null);
        }

        @Override
        public int hashCode() {
            int result = first != null ? first.hashCode() : 0;
            result = 31 * result + (second != null ? second.hashCode() : 0);
            return result;
        }

        public Pair<V, U> swap() {
            return makePair(second, first);
        }

        @Override
        public String toString() {
            return "(" + first + "," + second + ")";
        }

        @SuppressWarnings({ "unchecked" })
        public int compareTo(Pair<U, V> o) {
            int value = ((Comparable<U>) first).compareTo(o.first);
            if (value != 0) {
                return value;
            }
            return ((Comparable<V>) second).compareTo(o.second);
        }
    }

    private static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner() throws FileNotFoundException {

            if (System.getProperty("os.name").equals("Mac OS X")) {
                // Input is a file
                br = new BufferedReader(new FileReader("input.txt"));

                // PrintWriter class prints formatted representations
                // of objects to a text-output stream.
                PrintStream pw = new PrintStream(new FileOutputStream("output.txt"));
                System.setOut(pw);
            } else {
                // Input is System.in
                br = new BufferedReader(new InputStreamReader(System.in), 32768);
                st = null;
            }

        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int i() {
            return Integer.parseInt(next());
        }

        int[] intArray(int n) {
            int[] ret = new int[n];
            for (int i = 0; i < n; i++)
                ret[i] = i();
            return ret;
        }

        ArrayList<Integer> intList(int n) {
            ArrayList<Integer> al = new ArrayList<>();
            for (int i = 0; i < n; i++)
                al.add(i());
            return al;
        }

        long l() {
            return Long.parseLong(next());
        }

        long[] longArray(int n) {
            long[] ret = new long[n];
            for (int i = 0; i < n; i++)
                ret[i] = l();
            return ret;
        }

        double[] doubleArray(int n) {
            double[] ret = new double[n];
            for (int i = 0; i < n; i++)
                ret[i] = l();
            return ret;
        }

        ArrayList<Long> longList(int n) {
            ArrayList<Long> al = new ArrayList<>();
            for (int i = 0; i < n; i++)
                al.add(l());
            return al;
        }

        double d() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    private static boolean arr[] = sieve(1000001);
    private static ArrayList<Long> primes = new ArrayList<>();
    private static int freq[] = new int[200005];
    private static int mod = (int) (1e9 + 7);
    private static final int IMAX = 2147483647;
    private static final int IMIN = -2147483648;
    private static final long LMAX = 9223372036854775807L;
    private static final long LMIN = -9223372036854775808L;
    private static FastScanner c;
    private static PrintWriter pw;
}