The beauty of an array $$$b$$$ of length $$$m$$$ (with $$$m \ge 2$$$) is defined as the largest value of $$$b_j - b_i$$$ over all pairs of indices $$$i$$$ and $$$j$$$ such that $$$1\le i \lt j\le m$$$. More formally, it is equal to $$$\max\limits_{1\le i \lt j\le m} (b_j - b_i)$$$. Note that the beauty might be negative if the array is strictly decreasing.

Hao and Alex play a turn-based game on an array $$$a$$$ of length $$$n$$$. Initially, all elements of the array are unlocked. The players take turns alternately, with Hao going first.

On Hao's turn, he selects one unlocked element from array $$$a$$$ and removes it.
On Alex's turn, he selects one unlocked element from array $$$a$$$ and locks it (so it can no longer be removed by Hao).

The game continues until all elements of $$$a$$$ are either locked or removed. It can be proven that the game lasts exactly $$$n$$$ turns, and exactly $$$\left\lfloor \frac{n}{2} \right\rfloor$$$ elements will remain locked in array $$$a$$$ at the end.

Hao wants to minimize the beauty of the final array of locked elements, while Alex wants to maximize it. Determine the beauty of the final array if both players play optimally.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$4\le n\le 10^5$$$) — the size of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array $$$a$$$.

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

Output

For each test case, output a single integer representing the beauty of the final array if both Hao and Alex play optimally.

Note

In the first test case, the game may proceed as follows. Bolded elements are locked by Alex:

Turn 1 (Hao): Remove element $$$1$$$ (at position $$$2$$$), resulting in $$$[5, 2, 3, 4]$$$.
Turn 2 (Alex): Lock element $$$3$$$ (at position $$$3$$$), resulting in $$$[5, 2, \mathbf{3}, 4]$$$.
Turn 3 (Hao): Remove element $$$2$$$ (at position $$$2$$$), resulting in $$$[5, \mathbf{3}, 4]$$$.
Turn 4 (Alex): Lock element $$$4$$$ (at position $$$3$$$), resulting in $$$[5, \mathbf{3}, \mathbf{4}]$$$.
Turn 5 (Hao): Remove element $$$5$$$ (at position $$$1$$$), resulting in $$$[\mathbf{3}, \mathbf{4}]$$$.

The beauty of the final array $$$b = [3, 4]$$$ is equal to $$$b_2 - b_1 = 4 - 3 = 1$$$.

In the second test case, note that the answer might be negative:

Turn 1 (Hao): Remove element $$$2$$$ (at position $$$3$$$), resulting in $$$[3, 1, 1]$$$.
Turn 2 (Alex): Lock element $$$1$$$ (at position $$$2$$$), resulting in $$$[3, \textbf{1}, 1]$$$.
Turn 3 (Hao): Remove element $$$1$$$ (at position $$$3$$$), resulting in $$$[3, \textbf{1}]$$$.
Turn 4 (Alex): Lock element $$$3$$$ (at position $$$1$$$), resulting in $$$[\textbf{3}, \textbf{1}]$$$.

The beauty of the final array $$$b = [3, 1]$$$ is equal to $$$b_2 - b_1 = 1 - 3 = -2$$$.

In the third test case, one possible final array (assuming optimal play by both players) is $$$b = [3, 5, 8, 5, 1]$$$. The beauty, which is the largest difference $$$b_j - b_i$$$ over all pairs of indices $$$i$$$ and $$$j$$$ such that $$$1\le i \lt j\le 5$$$, is equal to $$$b_3 - b_1 = 8 - 3 = 5$$$.

Best Time to Buy and Sell Stock

Examples