题目描述

本市推出了一档热门真人秀节目《非常规配对》。根据节目规则，参与者的配对方式不同寻常：在人数偶数的情况下，所有参与者必须成双成对。

现在有一个由 $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$）——测试用例数。接下来给出 $t$ 个测试用例。

每个测试用例包含两行：

• 第 $1$ 行：一个偶数 $n$（$2\le n\le 2\cdot 10^5$），表示数组长度。
• 第 $2$ 行：$n$ 个整数 $a_1,a_2,\dots,a_n$（$-10^9\le a_i\le 10^9$），以空格分隔。

保证所有测试用例的 $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$。
• 第二个样例：数组为 $[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$。