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

В городе запустили популярное реалити-шоу Неклассические пары. По правилам шоу участников разбивают на пары необычным образом: при чётном количестве человек все участники обязательно окажутся в паре.

У Пети есть массив из $$$n$$$ целых чисел $$$a_1,a_2,\dots ,a_n$$$. Известно, что $$$n$$$ — чётное. Петя должен разбить участников-числа на ровно $$$\large\frac{n}{2}$$$ пар $$$(a_{p_1},a_{q_1}),\,(a_{p_2},a_{q_2}),\dots\,(a_{p_\frac{n}{2}},a_{q_\frac{n}{2}})$$$. Каждый индекс может входить не более чем в одну пару.

Для пары $$$(x,y)$$$ её разницей считается $$$|x-y|$$$. Петя хочет подобрать неклассические пары так, чтобы максимальная разница среди всех пар была как можно меньше.

Определите минимально возможное значение этой максимальной разницы.

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

Каждый тест состоит из нескольких наборов входных данных.

В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно чётное число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — длина массива $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1,a_2,\dots ,a_n$$$ $$$(-10^{9} \le a_i \le 10^{9})$$$ — элементы массива $$$a$$$.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

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

В первом наборе входных данных массив: $$$[1,2]$$$. Единственная возможная (и, следовательно, оптимальная) пара — $$$(1,2)$$$, её разность равна $$$|1-2| = 1$$$, ответ $$$1$$$.

Во втором наборе входных данных массив: $$$[10,1,2,9]$$$. Мы можем выбрать пары — $$$(1,2)$$$ и $$$(9,10)$$$: обе разности равны $$$1$$$, следовательно, максимальная разность равна $$$1$$$.

В третьем наборе входных данных массив: $$$[3,8,9,3,3,2]$$$. Мы можем выбрать пары: $$$(2,3)$$$, $$$(3,3)$$$, $$$(8,9)$$$. Разности: $$$1,0,1$$$ — наибольшая равна $$$1$$$.