题目描述

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

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

输入格式

第一行输入整数t，表示测试数据的个数，满足t≤20。 对于每组测试数据：

1. 第一行输入整数n，表示人数（即药物份数），满足2≤n≤50。
2. 第二行输入n个整数，表示原有n份药物的用量，每份用量在1到1000000000之间。

输出格式

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

样例输入

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

样例输出

3
0
4