This is the easy version of a problem. The only difference between an easy and a hard version is the constraints on $t$ and $n$. You can make hacks only if both versions of the problem are solved.

Arthur is giving a lesson to his famous $2 n$ knights. Like any other students, they're sitting at the desks in pairs, but out of habit in a circle. The knight $2 i - 1$ is sitting at the desk with the knight $2 i$.

Each knight has intelligence, which can be measured by an integer. Let's denote the intelligence of the $i$-th knight as $a_i$. Arthur wants the maximal difference in total intelligence over all pairs of desks to be as small as possible. More formally, he wants to minimize $\max\limits_{1 \le i \le n} (a_{2 i - 1} + a_{2 i}) - \min\limits_{1 \le i \le n} (a_{2 i - 1} + a_{2 i})$.

However, the Code of Chivalry only allows swapping the opposite knights in the circle, i.e., Arthur can simultaneously perform $a_i := a_{i + n}$, $a_{i + n} := a_i$ for any $1 \le i \le n$. Arthur can make any number of such swaps. What is the best result he can achieve?

Input

Each test consists of several test cases. The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. It is followed by descriptions of the test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2000$) — the number of desks.

The second line consists of $2n$ integers $a_1, a_2, \ldots, a_{2 n}$ ($1 \le a_i \le 10^9$) — the intelligence values of the knights.

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

Output

For each test case, output a single line containing one integer — the minimal difference Arthur can achieve.

见题面 Input 部分

见题面 Output 部分

In the first test case, Arthur can swap the second and the fourth knights. Then the total intelligence at both desks will be $10$.

In the third test case, Arthur can make $0$ operations, which will result in the total intelligence of $11$ at each of the desks.

In the fourth test case, Arthur can swap knights with indices $2$ and $5$ and achieve the difference of $2$. It can be proven that he cannot improve his result any further.