题目描述

最近实验室的小伙伴们得了怪病，他们会按病重程度严格递增的顺序去看医生。因此医生需要配置用量严格递增的药物，且不能调换各药物的顺序。

医生可以在原有药物用量的基础上，对每份药物增加或减少不超过 $x$ 的用量（减少后剩余用量不能小于 $1$），以此让药物用量满足严格递增的要求。医生想节约药物，需要确定满足条件的最小 $x$，请你帮忙求出这个最小的 $x$。

输入格式

第一行输入一个整数 $t$，表示测试数据的个数。

对于每组测试数据：

• 第一行输入一个整数 $n$，表示药物份数；
• 第二行输入 $n$ 个整数，表示原有 $n$ 份药物的用量，相邻整数之间用一个空格隔开。

输出格式

对于每组测试数据，输出一行一个整数，表示满足条件的最小 $x$。

样例

3
3
9 5 11
2
5 8
5
1 1 1 1 1

3
0
4

样例解释

• 第一组数据：原有用量 $[9, 5, 11]$，需要调整为严格递增序列。当 $x=3$ 时，可以调整为 $[6, 8, 12]$ 或 $[7, 8, 11]$ 等，满足每项增减不超过 $3$ 且严格递增，且无法用更小的 $x$ 完成。
• 第二组数据：原有用量 $[5, 8]$，已经严格递增且无需调整，故 $x=0$。
• 第三组数据：原有用量全是 $1$，要严格递增，至少需要将第二个变成 $2$，第三个变成 $3$，第四个变成 $4$，第五个变成 $5$，变化量最大为 $4$，故 $x=4$。

数据范围

• $1 \le t \le 20$
• $2 \le n \le 50$
• 原有每份用量为 $1$ 到 $10^9$ 之间的整数