C. Range Minimization
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer array $$$a$$$ of length $$$n$$$.

In one operation, you may choose two distinct indices $$$i,j$$$ satisfying

$$$$$$ 1\le i,j\le n,\qquad i\ne j, $$$$$$

and perform the following changes simultaneously:

$$$$$$ a_i\gets a_i+3,\qquad a_j\gets a_j-1. $$$$$$

You may perform any finite number of operations, including zero operations. The elements of the array are allowed to become negative during the process.

The range of an array is defined as

$$$$$$ \max_i a_i-\min_i a_i. $$$$$$

Find the minimum possible range of the array after performing any number of operations.

Input

The first line contains a single integer $$$T$$$ — the number of test cases.

Each test case consists of two lines:

The first line contains a single integer $$$n$$$ — the length of the array. The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ — the initial array.

The following constraints hold:

$$$$$$ 1\le T\le 10^4, $$$$$$

$$$$$$ 1\le n\le 2\times 10^5, $$$$$$

$$$$$$ -10^9\le a_i\le 10^9. $$$$$$

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed

$$$$$$ 2\times 10^5. $$$$$$

Output

For each test case, output a single integer — the minimum possible range of the array after performing any finite number of operations.

Example
Input
3
1
5
2
0 2
4
-1 9 5 8
Output
0
2
1