称长度为 $n$ 的数组 $a$ 为有序（sorted），当且仅当满足：

$a_1 \le a_2 \le \dots \le a_{n-1} \le a_n$

Ntarsis 有一个长度为 $n$ 的数组 $a$。

他可以对数组执行如下操作（可执行 $0$ 次或多次）：

• 选择一个下标 $i$（$1 \le i \le n-1$）；
• 将 $a_1,a_2,\dots,a_i$ 都加 $1$；
• 将 $a_{i+1},a_{i+2},\dots,a_n$ 都减 $1$。

执行操作后，数组元素允许变为负数。

请你求出：使数组 $a$ 变得不有序（not sorted）所需的最少操作次数。

输入格式

输入包含多组测试用例。第一行一个整数 $t$（$1 \le t \le 100$），表示测试用例数量。

每个测试用例：

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

保证所有测试用例的 $n$ 之和不超过 $500$。

输出格式

对每个测试用例输出一行一个整数，表示将数组变为不有序所需的最少操作次数。

样例

输入

4
2
1 1
4
1 8 10 13
3
1 3 2
3
1 9 14

输出

1
2
0
3

说明

• 第 1 组：选择 $i=1$，数组变为 $[2,0]$，已不有序。
• 第 3 组：原数组已经不有序，因此答案为 $0$。