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.
import sys
import math
from math import gcd,sqrt
import heapq as hq
from bisect import bisect_right, bisect_left, bisect
import itertools

# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

from sys import stdin, stdout, setrecursionlimit
def isPowerOfTwo(x):
    return (x and (not(x & (x - 1))))

MOD = int(1e9) + 7
alp = 'abcdefghijklmnopqrstuvwxyz'
v = {'a':1, 'e':1, 'i':1, 'o':1, 'u':1}
c = {}
for i in alp:
    if i not in v:
        c[i] = 1
T = 1
T = int(stdin.readline())
for _ in range(T):
    n = int(stdin.readline())
    # b = list(map(int, stdin.readline().rstrip().split()))
    a = list(map(int, stdin.readline().rstrip().split()))
    # digits = list(stdin.readline().strip('\n'))
    # a = list(stdin.readline().strip('\n'))
    # b = list(stdin.readline().strip('\n'))
    # t = str(stdin.readline().strip('\n'))
    a.sort()
    mn = 1e7 + 1
    for i in range(2*n):
        mn = min(mn, abs(a[-1]- a[0]))
        a[-1] -= 1
        a[0] += 1
        a.sort()
    print(mn)