1624A. Plus One on the Subset

time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output

Polycarp got an array of integers a[1…n] as a gift. Now he wants to perform a certain number of operations (possibly zero) so that all elements of the array become the same (that is, to become a $_{1}$ =a $_{2}$ =⋯=a $_{n}$ ).

Polycarp得到了一个整数数组a[1…n]作为礼物。现在，他希望执行一定数量的操作（可能为零），使数组的所有元素变得相同（也就是说，变成a $_{1}$ =a $_{2}$ =⋯=a $_{n}$ ）。

In one operation, he can take some indices in the array and increase the elements of the array at those indices by 1.

在一次操作中，他可以获取数组中的一些索引，并将这些索引处的数组元素增加1。

For example, let a=[4,2,1,6,2]. He can perform the following operation: select indices 1, 2, and 4 and increase elements of the array in those indices by 1. As a result, in one operation, he can get a new state of the array a=[5,3,1,7,2].

例如，设a=[4,2,1,6,2]。他可以执行以下操作：选择索引1、2和4，并将这些索引中的数组元素增加1。因此，在一次操作中，他可以得到数组a=[5,3,1,7,2]的新状态。

What is the minimum number of operations it can take so that all elements of the array become equal to each other (that is, to become a $_{1}$ =a $_{2}$ =⋯=a $_{n}$ )?

为了使数组中的所有元素彼此相等（即变为a $_{1}$ =a $_{2}$ =⋯=a $_{n}$ ），它可以进行的最小操作数是多少？

Input

The first line of the input contains a single integer t (1≤t≤10 $^{4}$ ) — the number of test cases in the test.

输入的第一行包含一个整数t（1≤T≤10 $^{4}$ ）-测试中的测试用例数。

The following are descriptions of the input test cases.

以下是输入测试用例的描述。

The first line of the description of each test case contains one integer n (1≤n≤50) — the array a.

每个测试用例描述的第一行包含一个整数n（1）≤N≤50）-阵列a。

The second line of the description of each test case contains n integers a $_{1}$ ,a $_{2}$ ,⋯,a $_{n}$ (1≤a $_{i}$ ≤10 $^{9}$ ) — elements of the array a.

每个测试用例描述的第二行包含n个整数 a $_{1}$ ,a $_{2}$ ,⋯,a $_{n}$ (1≤a $_{i}$ ≤10 $^{9}$ )-数组a的元素。

Output

For each test case, print one integer — the minimum number of operations to make all elements of the array a equal.

对于每个测试用例，打印一个整数——使数组的所有元素相等的最小操作数

Example

input

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

output

3
4
1

Note

First test case:

a=[3,4,2,4,1,2] take a3,a5 and perform an operation plus one on them, as a result we get a=[3,4,3,4,2,2]. a=[3,4,3,4,2,2] we take a1,a5,a6 and perform an operation on them plus one, as a result we get a=[4,4,3,4,3,3]. a=[4,4,3,4,3,3] we take a3,a5,a6 and perform an operation on them plus one, as a result we get a=[4,4,4,4,4,4]. There are other sequences of 3 operations, after the application of which all elements become equal.

Second test case:

a=[1000,1002,998] 2 times we take a1,a3 and perform an operation plus one on them, as a result we get a=[1002,1002,1000]. a=[1002,1002,1000] also take a3 2 times and perform an operation plus one on it, as a result we get a=[1002,1002,1002].

Third test case:

a=[12,11] take a2 and perform an operation plus one on it, as a result we get a=[12,12].

Solution

Code

#include <iostream>
using namespace  std;
//A.Plus One on the Subset
int main() {
    int t = 0;
    cin >> t;
    for(int i = 0;i < t;i++){
        int n = 0;
        cin >> n;
        int a[n];
        cin >> a[0];
        int max = a[0];
        int min = a[0];
        for(int j=1;j<n;j++){
            cin >> a[j];
            if(a[j] <= min){
                min = a[j];
            }
            if(a[j] >= max) {
                max = a[j];
            }
        }
        cout<<max-min<<endl;
    }
    return 0;
}