题目描述

一个数组的极差定义为其最大元素与最小元素之差。

给定一个长度为 $n$ 的整数数组 $a$。你可以执行若干次以下操作（也可以不执行）：

• 选择两个不同的下标 $i,j$（$1\le i,j\le n$ 且 $i\ne j$），然后按以下操作赋值：$$a_i\leftarrow a_i+3,\qquad a_j\leftarrow a_j-1.$$

请计算经过若干次操作后，数组 $a$ 的极差的最小值。

输入格式

本题有多组测试数据。

第一行包含一个整数 $T$（$1\le T\le 10^4$），表示测试用例的数量。

对于每组测试用例：

• 第一行包含一个整数 $n$（$1\le n\le 2\times 10^5$），表示数组 $a$ 的长度；
• 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$-10^9\le a_i\le 10^9$），表示数组 $a$ 中的元素。

保证所有测试用例的 $n$ 之和不超过 $2\times 10^5$。

输出格式

对于每组测试用例，输出一行一个整数，表示经过任意有限次操作后能够得到的最小极差。

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

0
2
1

提示

第一组测试用例只有一个元素，因此极差恒为 $0$。