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.
from typing import DefaultDict
from math import sqrt
from collections import OrderedDict, defaultdict
import math
from sys import maxsize

def sieve_erasthones(n):
    #prime number less than equal to n
    #complexixty n*log(log(n))
    cnt=0
    prime=[True for i in range(n+1)]
    p=2
    while (p*p<=n):
        if (prime[p]==True):
            for i in range(p**2,n+1,p):
                prime[i]=False
        p+=1
    prime[0]=False 
    prime[1]=False 
    for p in range(n+1):
        if prime[p]:
            cnt+=1 
    return cnt

def calculate(p,q):
    mod = 998244353
    expo = 0 
    expo = mod - 2 
    while (expo):
        if (expo & 1):
            p = (p*q)%mod
        q = (q*q)%mod
        expo >>= 1 
    return p

def count_factors(n):
    i=1
    c=0
    while i<=math.sqrt(n):
        if n%i==0:
            if n//i==i:
                c+=1
            else:
                c+=2
        i+=1
    return c

def ncr_modulo(n, r, p):
    num = den = 1
    for i in range(r):
        num = (num * (n - i)) % p
        den = (den * (i + 1)) % p
    return (num * pow(den,
            p - 2, p)) % p

def isprime(n):
    prime_flag = 0
    if(n > 1):
        for i in range(2, int(sqrt(n)) + 1):
            if (n % i == 0):
                prime_flag = 1
                break
        if (prime_flag == 0):
            return True 
        else:
            return False
    else:
        return True

def smallestDivisor(n):  
    if (n % 2 == 0):
        return 2
    i = 3
    while(i * i <= n): 
        if (n % i == 0):
            return i
        i += 2
    return n

def dict_ele_count(l):
    d=DefaultDict(lambda:0)
    for ele in l:
        d[ele]+=1
    return d 

def max_in_dict(d):
    maxi=0
    for ele in d:
        if d[ele]>maxi:
            maxi=d[ele]
    return maxi

def element_count(s):
    # returns 2-D list of elements and its count
    l=[]
    k=s[0]
    c=0
    for ele in s:
        if ele==k:
            c+=1 
        else:
            l.append([k,c])
            k=ele 
            c=1
    l.append([k,c])
    return l

def modular_exponentiation(x,y,p): 
    res = 1  
    x=x%p 
    if x==0:
        return 0

    while (y > 0):
        if ((y & 1) != 0):
            res = (res * x)%p
        y = y >> 1 
        x = (x * x)%p

    return res


bool=True
flag=True
mod= 10**9 + 7
ans=0
d=defaultdict(lambda:0)
vowels=['a','e','i','o','u']

for _ in range(int(input())):
    n=int(input())
    l=list(map(int,input().split()))
    # l2=list(map(int,input().split()))
    print(sum(l)%n)
    
