A. Выбор трех палочек
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть $$$n$$$ палочек с положительными целочисленными длинами $$$a_1, a_2, \ldots, a_n$$$.

Вы можете выполнить следующую операцию произвольное число раз (возможно, ноль):

  • выберите одну палочку, затем увеличьте или уменьшите ее длину на $$$1$$$. После каждой операции длины всех палочек должны остаться положительными.

Какое минимальное число операций необходимо, чтобы вы могли выбрать три палочки из данных $$$n$$$ и сложить их, не ломая, в равносторонний треугольник?

Равносторонним треугольником называется треугольник, у которого все три стороны равны.

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

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

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$3 \le n \le 300$$$) — количество палочек.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — длины палочек.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$300$$$.

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

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

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

В первом примере можно увеличить длину первой палочки на $$$1$$$, затем уменьшить длину третьей палочки на $$$1$$$. Всего вы сделаете $$$2$$$ операции, и сможете взять три палочки, чтобы собрать равносторонний треугольник с длиной стороны $$$2$$$.

In the fourth test case, you can decrease the length of the seventh stick by $$$1$$$. An equilateral triangle of side length $$$1$$$ can be selected and formed by the second, fourth, and seventh sticks.