题目描述

Polycarp 收到了一份整数数组 $a[1 \dots n]$ 作为礼物。现在他希望通过若干次操作（可以为零次），使得数组中的所有元素都变成相同的值（即 $a_1=a_2=\dots=a_n$）。

• 每次操作时，他可以选择数组中的若干个下标，并将这些下标对应的数组元素都加 $1$。

例如，设 $a=[4,2,1,6,2]$。他可以进行如下操作：选择下标 $1,2,4$，并将这些位置上的元素都加 $1$。操作后，数组变为 $a=[5,3,1,7,2]$。

请问，最少需要多少次操作，才能使数组 $a$ 的所有元素都相等（即 $a_1=a_2=\dots=a_n$）？

输入格式

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

接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 50$），表示数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示数组 $a$ 的元素。

输出格式

对于每个测试用例，输出一个整数，表示将数组 $a$ 的所有元素变为相等所需的最少操作次数。

说明/提示

第一个测试用例：

• $a=[3,4,2,4,1,2]$，选择 $a_3, a_5$ 并对它们执行加一操作，结果为 $a=[3,4,3,4,2,2]$。
• $a=[3,4,3,4,2,2]$，选择 $a_1, a_5, a_6$ 并对它们执行加一操作，结果为 $a=[4,4,3,4,3,3]$。
• $a=[4,4,3,4,3,3]$，选择 $a_3, a_5, a_6$ 并对它们执行加一操作，结果为 $a=[4,4,4,4,4,4]$。

还有其他 $3$ 次操作的方案，也能使所有元素相等。

第二个测试用例：

• $a=[1000,1002,998]$，两次选择 $a_1, a_3$ 并执行加一操作，结果为 $a=[1002,1002,1000]$。
• $a=[1002,1002,1000]$，再两次选择 $a_3$ 并执行加一操作，结果为 $a=[1002,1002,1002]$。

第三个测试用例：

• $a=[12,11]$，选择 $a_2$ 并执行加一操作，结果为 $a=[12,12]$。

由 ChatGPT 4.1 翻译

样例

3
6
3 4 2 4 1 2
3
1000 1002 998
2
12 11

3
4
1