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.
//package File;
import java.io.BufferedReader;
import java.math.BigInteger;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
//For submitting solution in KickStart change class name from C1 to Solution then submit it
//and for AtCoder class name should be Main
public class Solution {
//.i() for integer,.nl() for string, .l() for long
	public static class pair implements Comparable<pair>{
        String index;
        int weight;
        pair(String index,int weight){
            this.index=index;
            this.weight=weight;
        }
        public int compareTo(pair o){
            return this.weight-o.weight;
        }
    }
	public static class pair1 implements Comparable<pair1>{
		long first;
		long second;
		pair1(long first,long second){
			this.first=first;
			this.second=second;
		}
		public int compareTo(pair1 o) {
			return (int)(this.first-o.first);
		}
	}
	public static long mul(long a,long b) {
		long res = 0; 
	    while (b > 0)
	    {
	        if ((b & 1)==1) {
	            res = res + a;
	        }
	 
	        a = a << 1;
	        b = b >> 1;
	    }
	    return res;
	}
	
	public static void sieve(int n,ArrayList<Integer>l) {
		boolean prime[] = new boolean[n + 1];
        for (int i = 0; i <= n; i++)
            prime[i] = true;
 
        for (int p = 2; p * p <= n; p++)
        {
            if (prime[p] == true)
            {
                for (int i = p * p; i <= n; i += p)
                    prime[i] = false;
            }
        }
        for (int i = 2; i <= n; i++)
        {
            if (prime[i] == true)
            	l.add(i);
                //System.out.print(i + " ");
        }
	}
	
	public static long check(long x)
    {
       
        // check for the set bits
        x |= x >> 1;
        x |= x >> 2;
        x |= x >> 4;
        x |= x >> 8;
        x |= x >> 16;
        return x ^ (x >> 1); 
     
    }
	
	public static void main(String[] args) {
		FastScanner sc=new FastScanner();
		int t=sc.i();
		while(t-->0) {
			int n=sc.i();
			long array[]=new long[n];
			for(int i=0;i<n;i++) {
				array[i]=sc.l();
			}
			Arrays.sort(array);
			for(int i=1;i<n-1;i++) {
				array[i]=array[i]-1;
			}
			long sum=0;
			for(int i=1;i<n-1;i++) {
				sum+=array[i];
			}
			if(array[0]+sum>=array[n-1]) {
				System.out.println(0);
			}
			else {
				System.out.println(array[n-1]-array[0]-sum);
			}
		}
	}
	static long gcd(long a,long b) {
		if(a==0) {
			return b;
		}
		return gcd(b%a,a);
	}
	static long lcm(long a, long b) {
		return (a*b)/gcd(a,b);
	}
	static boolean  isPrime(long n) {
		if(n <=1 )return false;
		if(n==2) return true;
		if(n%2==0) return false;
		for(int i=3;i<=Math.sqrt(n);i+=2)
			if(n%i==0) return false;
		return true;
	}
	private static int countDigits(int l) {
		if (l >= 1000000000) return 10;
		if (l >= 100000000) return 9;
		if (l >= 10000000) return 8;
		if (l >= 1000000) return 7;
		if (l >= 100000) return 6;
		if (l >= 10000) return 5;
		if (l >= 1000) return 4;
		if (l >= 100) return 3;
		if (l >= 10) return 2;
		return 1;
	}
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;
	}
    static boolean isPalindrome(String s,int start,int end) {
    	if(s.length()==0 || s.length()==1) {
    		return true;
    	}
    	 if(s.charAt(start)!=s.charAt(end)) {
    		return false;
    	}
    	 if(start<end+1) {
    	return isPalindrome(s,start+1,end-1);
    	 }
    	 return true;
    }
}
 
class FastScanner {
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st=new StringTokenizer("");
    String n() {
        while (!st.hasMoreTokens())
            try {
                st=new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        return st.nextToken();
    }
    int[] ia(int n) {
    	int[] arr = new int[n];
    	for(int i=0;i<n;i++)
    		arr[i] = i();
    	return arr;
    }
    String[] sa(int n) {
    	String[] arr = new String[n];
    	for(int i=0;i<n;i++)
    		arr[i] = n();
    	return arr;
    }
    long[] la(int n) {
    	long[] arr = new long[n];
    	for(int i=0;i<n;i++)
    		arr[i] = l();
    	return arr;
    }
     String nl()
    {
        String str = "";
        try
        {
            str = br.readLine();
        }
        catch (IOException e)
        {
            e.printStackTrace();
        }
        return str;
    }
 
    int i() {
        return Integer.parseInt(n());
    }
    long l() {
        return Long.parseLong(n());
    }
}