该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Polycarp 收到一个整数数组 $a[1\dots n]$ 作为礼物。现在他想进行若干次操作（也可以是 $0$ 次），使得数组中所有元素都变为相同，即满足：

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

例如，若 $a=[4,2,1,6,2]$，他可以选择下标 $1,2,4$ 并将对应元素加一，操作后数组变为 $[5,3,1,7,2]$。

请你计算：最少需要多少次操作，才能使数组所有元素相等？

输入格式

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

每个测试用例包含：

• 第一行一个整数 $n$（$1\le n\le 50$），表示数组长度。
• 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1\le a_i\le 10^9$），表示数组元素。

输出格式

对每个测试用例输出一行一个整数：使数组所有元素相等所需的最少操作次数。

样例

输入

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

输出

3
4
1

说明

第 1 组：

• $[3,4,2,4,1,2]$ 选 $a_3,a_5$ 加一 $\to [3,4,3,4,2,2]$
• 选 $a_1,a_5,a_6$ 加一 $\to [4,4,3,4,3,3]$
• 选 $a_3,a_5,a_6$ 加一 $\to [4,4,4,4,4,4]$ 共 $3$ 次。

第 2 组：

• $[1000,1002,998]$ 两次选择 $a_1,a_3$ 加一 $\to [1002,1002,1000]$
• 再两次选择 $a_3$ 加一 $\to [1002,1002,1002]$ 共 $4$ 次。

第 3 组：

• $[12,11]$ 选择 $a_2$ 加一 $\to [12,12]$ 共 $1$ 次。