Problem Description

The range spread of an array is defined as the difference between its maximum element and its minimum element.

Given an integer array $a$ of length $n$, you may perform the following operation any number of times (including zero times):

• Choose two different indices $i, j$ ($1 \le i, j \le n$ and $i \ne j$), then update:$$a_i \leftarrow a_i + 3,\qquad a_j \leftarrow a_j - 1.$$

Compute the minimum possible range spread of array $a$ after performing some operations.

Input Format

This problem contains multiple testcases.

The first line contains an integer $T$ ($1 \le T \le 10^4$), the number of testcases.

For each testcase:

• The first line contains an integer $n$ ($1 \le n \le 2 \times 10^5$), the length of array $a$.
• The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^9 \le a_i \le 10^9$), the elements of array $a$.

It is guaranteed that the sum of $n$ over all testcases does not exceed $2 \times 10^5$.

Output Format

For each testcase, output one integer per line, the minimum range spread that can be achieved after any finite number of operations.

3
1
5
2
0 2
4
-1 9 5 8

0
2
1

Hint

In the first testcase, there is only one element, so the range spread is always $0$.

Translated by ChatGPT 5