human
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.
Solve the task in PYTHON3.

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.

# import heapq
# import copy
# from collections import deque
# import sys
# import bisect

# def cost(a, b):
#     return abs(a-b)

# def solve(n, arr):
#     arr.sort()
#     arr = deque(arr)
#     maxh = arr.pop()
#     minh = arr.popleft()
#     prev = abs(maxh-minh)
#     ct = prev
#     ctct = 0
#     if ct < 2:
#         return ct
#     change = True
#     while change:
#         maxh = maxh-ct//2
#         minh = minh+ct//2
#         bisect.insort(arr, maxh)
#         bisect.insort(arr, minh)
#         maxh = arr.pop()
#         minh = arr.popleft()
#         ct = abs(maxh-minh)
#         if ct == prev:
#             if ctct < n:
#                 ctct += 1
#             else:
#                 change = False
#         else:
#             prev = ct
#             ctct = 0

#     return ct

def fsolve(n, arr):
    s = sum(arr)
    if s % n == 0:
        return 0
    else:
        return 1
    # minheap = heapq.heapify(copy(arr))
    # maxheap = [-1*i for i in arr]
    # maxheap = heapq.heapify(copy(maxheap))
    # nochange = False
    # while (minheap[0]-abs(maxheap[0])) != 0 and not nochange:
    #     maxh = abs(heapq.heappop(maxheap))
    #     minh = abs(heapq.heappop(minheap))
    #     cost = maxh-minh
    #     if cost == 0:
    #         return 0
    #     else:
    #         maxh = maxh - cost//2
    #         minh = minh + cost//2
    #         heapq.heappush(maxheap)

if __name__ == "__main__":
    t = int(input())
    for i in range(t):
        n = int(input())
        arr = list(map(int, input().rstrip().split()))
        ans = fsolve(n, arr)
        print(ans)