B. Черные клетки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задана полоска, разделенная на клетки, клетки пронумерованы слева направо от $$$0$$$ до $$$10^{18}$$$. Изначально все клетки белые.

Вы можете выполнять следующее действие: выбрать две белые клетки $$$i$$$ и $$$j$$$, такие что $$$i \ne j$$$ и $$$|i - j| \le k$$$, и покрасить их в черный цвет.

Задан список $$$a$$$. Все клетки из этого списка должны быть покрашены в чёрный. Также в черный цвет может быть покрашено не более одной клетки, не входящей в этот список. Ваша задача — определить, для какого минимального значения $$$k$$$ это возможно.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 2000$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 < a_i < 10^{18}$$$; $$$a_i < a_{i + 1}$$$).

Дополнительное ограничение на входные данные: сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2000$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — минимальное значение $$$k$$$, для которого возможно покрасить все заданные клетки.

Пример
Входные данные
4
2
1 2
1
7
3
2 4 9
5
1 5 8 10 13
Выходные данные
1
1
2
3
Примечание

В первом наборе входных данных с параметром $$$k=1$$$ можно покрасить клетки $$$(1, 2)$$$.

Во втором наборе входных данных с параметром $$$k=1$$$ можно покрасить клетки $$$(7, 8)$$$.

В третьем наборе входных данных с параметром $$$k=2$$$ можно покрасить клетки $$$(2, 4)$$$ и $$$(8, 9)$$$.

В четвертом наборе входных данных с параметром $$$k=3$$$ можно покрасить клетки $$$(0, 1)$$$, $$$(5, 8)$$$ и $$$(10, 13)$$$.