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

public class Dubstep{

public static void main(String[] args) 
     {
		FastScanner fs= new FastScanner();
	    int t=fs.nextInt();
	    while(t-->0)
	    {
	    	int n=fs.nextInt();
	    	int sum=0;
	    	int arr[]=new int[n];
	    	int min=Integer.MAX_VALUE,max=Integer.MIN_VALUE;
	    	for(int i=0;i<n;i++)
	    	{
	    		arr[i]=fs.nextInt();
	    	    if(arr[i]>max)
	    	    {
	    	    	max=arr[i];
	    	    }
	    		if(arr[i]<min)
	    		{
	    			min=arr[i];
	    		}
	    	}
//	    	System.out.println(max+" max "+min+"min ");
	    	int a=Integer.MIN_VALUE;
	    	
	    	for(int i=0;i<n;i++)
	    	{
	    		if(arr[i]!=max)
	    		{
	    			a=Math.max(a, arr[i]);
	    		}
	    	}
	    	if(a==Integer.MIN_VALUE)
	    	{
	    		a=0;
	    	}
	    	System.out.println(max-min-a);
	    	
	    }
		
     }
}
class FastScanner {
	//I don't understand how this works lmao
	private int BS = 1 << 16;
	private char NC = (char) 0;
	private byte[] buf = new byte[BS];
	private int bId = 0, size = 0;
	private char c = NC;
	private double cnt = 1;
	private BufferedInputStream in;

	public FastScanner() {
		in = new BufferedInputStream(System.in, BS);
	}

	public FastScanner(String s) {
		try {
			in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
		} catch (Exception e) {
			in = new BufferedInputStream(System.in, BS);
		}
	}

	private char getChar() {
		while (bId == size) {
			try {
				size = in.read(buf);
			} catch (Exception e) {
				return NC;
			}
			if (size == -1)
				return NC;
			bId = 0;
		}
		return (char) buf[bId++];
	}

	public int nextInt() {
		return (int) nextLong();
	}

	public int[] nextInts(int N) {
		int[] res = new int[N];
		for (int i = 0; i < N; i++) {
			res[i] = (int) nextLong();
		}
		return res;
	}

	public long[] nextLongs(int N) {
		long[] res = new long[N];
		for (int i = 0; i < N; i++) {
			res[i] = nextLong();
		}
		return res;
	}

	public long nextLong() {
		cnt = 1;
		boolean neg = false;
		if (c == NC)
			c = getChar();
		for (; (c < '0' || c > '9'); c = getChar()) {
			if (c == '-')
				neg = true;
		}
		long res = 0;
		for (; c >= '0' && c <= '9'; c = getChar()) {
			res = (res << 3) + (res << 1) + c - '0';
			cnt *= 10;
		}
		return neg ? -res : res;
	}

	public double nextDouble() {
		double cur = nextLong();
		return c != '.' ? cur : cur + nextLong() / cnt;
	}

	public double[] nextDoubles(int N) {
		double[] res = new double[N];
		for (int i = 0; i < N; i++) {
			res[i] = nextDouble();
		}
		return res;
	}

	public String next() {
		StringBuilder res = new StringBuilder();
		while (c <= 32)
			c = getChar();
		while (c > 32) {
			res.append(c);
			c = getChar();
		}
		return res.toString();
	}

	public String nextLine() {
		StringBuilder res = new StringBuilder();
		while (c <= 32)
			c = getChar();
		while (c != '\n') {
			res.append(c);
			c = getChar();
		}
		return res.toString();
	}

	public boolean hasNext() {
		if (c > 32)
			return true;
		while (true) {
			c = getChar();
			if (c == NC)
				return false;
			else if (c > 32)
				return true;
		}
	}
}
