C. Bed Building
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Munir is building his new bed from IKAE! He has already dumped all his wood of lengths $$$a_1,a_2,\dots,a_n$$$ on the floor. Now the first step is to build the bed frame.

The bed frame should consist of two pieces of length $$$x$$$, and two of length $$$y$$$ (possibly with $$$x=y$$$). Unfortunately, IKAE does not have very good quality control, so he finds that he might not have two pairs of wood with the same lengths.

Instead, he tries to build an almost perfect bed frame. Specifically, he should pick distinct indices $$$i,j,k,l$$$ to minimize the deviation $$$|a_i-a_j|+|a_k-a_l|$$$.

Unfortunately he has too many pieces of wood, so he cannot do this by himself. Help him!!

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 2\cdot 10^5)$$$ — the number of wood planks Munir has.

The second line of each test case contains n integers $$$a_1,a_2,\dots,a_n\ (1\le a_i\le 10^{18})$$$ — the lengths of each wood plank.

It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2\cdot 10^5$$$

Output

For each test case, output a single integer: the smallest possible deviation of a bed frame given the wood lengths.

Example
Input
3
4
1 2 3 4
7
10 20 80 160 320 640 40
5
2 1 2 1 2
Output
2
50
0