human
Can you solve the below in PYTHON3?
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.
 ... Here's the minimum possible ugliness you can achieve, after any number of days?
assistant
#Here's the minimum possible ugliness you can achieve, after any number of days.

#!/usr/bin/env python

# जय श्री गणेश
#--MODULES BEGINS--
from __future__ import division, print_function
import sys
'''--python 2 and pypy begins--  - comment this line to run the below code
if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
# --python 2 and pypy ends--'''
import io, os, re, time, random
from io import BytesIO, IOBase
import math, functools, collections
# import bisect, heapq, numpy
# from contextlib import contextmanager
# from jinja2 import Template
#--MODULES ENDS--

#--SHORTHANDS BEGINS--
# input = raw_input
# input = sys.stdin.readline
# sys.stdout.flush()
# alphabets = "abcdefghijklmnopqrstuvwxyz"
# from statistics import mode
# from functools import reduce
# from bisect import bisect
# from collections import defaultdict
# from collections import Counter
# hp = defaultdict(lambda: 0)
# hp = collections.defaultdict(int, collections.Counter(lis))
# lis = sorted(hp.items(), key = lambda kv:(kv[1], kv[0]))
# lis = sorted(lis, key = lambda ele: (ele[1], ele[0]))
# lis = list(filter(lambda a: a[1] != min(hp.values()), lis))
# input = lambda: sys.stdin.readline().strip()
# imap = lambda: map(int,input().split())
# ilist = lambda: list(map(int, input().split()))
# sys.stdout.write(str(ans) + "\n")
# for line in sys.stdin
# except: print(f'Unknown Error: {sys.exc_info()[1]}')
# w = int(input()); print("YNEOS"[(w > 2 and not w % 2)::2]);

# return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right) if root else list()
#--SHORTHANDS ENDS--

#----    CODE BEGINS    ----->

#--GLOBAL VALUES BEGINS--
class ConstantMod:
    ''' Constant Values for Competitive Programming '''
    # __slots__ = ['_modd', '_maxx', ]  # for fixed number of attributes in __dict__ of the class's instance object
    def __init__(self, n = None, *args, **kwargs):
        self._modd = n
        # self.minn = -(n)
        self._maxx = kwargs['maxvalue'] if 'maxvalue' in kwargs else int(1e9 + 7)
       ...