B. Unconventional Pairstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputA popular reality show Unconventional Pairs has been launched in the city. According to the rules of the show, participants are paired in an unusual way: with an even number of people, all participants must be in pairs.Petya has an array of $$$n$$$ integers $$$a_1,a_2,\dots ,a_n$$$. It is known that $$$n$$$ is even. Petya must divide the participants (numbers) into exactly $$$\large\frac{n}{2}$$$ pairs $$$(a_{p_1},a_{q_1}),\,(a_{p_2},a_{q_2}),\dots\,(a_{p_\frac{n}{2}},a_{q_\frac{n}{2}})$$$. Each index can be included in no more than one pair.For a pair $$$(x,y)$$$, its difference is defined as $$$|x-y|$$$. Petya wants to form unconventional pairs such that the maximum difference among all pairs is minimized.Determine the minimum possible value of this maximum difference.InputEach test consists of several test cases.The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains one even number $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$.The second line contains $$$n$$$ integers $$$a_1,a_2,\dots ,a_n$$$ $$$(-10^{9} \le a_i \le 10^{9})$$$ — the elements of the array $$$a$$$.It is guaranteed that the sum of the values of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.OutputFor each test case, output a single number — the minimum possible maximum difference between the elements in pairs.ExampleInput521 2410 1 2 963 8 9 3 3 285 5 5 5 5 5 5 54-5 -1 2 6Output11104NoteIn the first test case, the array is: $$$[1,2]$$$. The only possible (and therefore optimal) pair is $$$(1,2)$$$, its difference is $$$|1-2| = 1$$$, the answer is $$$1$$$.In the second test case, the array is: $$$[10,1,2,9]$$$. We can choose pairs — $$$(1,2)$$$ and $$$(9,10)$$$: both differences are equal to $$$1$$$, therefore, the maximum difference is $$$1$$$.In the third test case, the array is: $$$[3,8,9,3,3,2]$$$. We can choose pairs: $$$(2,3)$$$, $$$(3,3)$$$, $$$(8,9)$$$. The differences are: $$$1,0,1$$$ — the largest is $$$1$$$.