E1. 让我给你上一课（简单版）

时间限制：每个测试点 $2$ 秒
内存限制：$256$ 兆字节

本题是某问题的简单版本。简单版本与困难版本唯一的区别在于 $t$ 和 $n$ 的约束条件不同。只有当两个版本都通过时，你才能进行 hacking 操作。

Arthur 正在给他著名的 $2n$ 名骑士上课。像其他学生一样，他们两两一组坐在课桌旁，但出于习惯，他们坐成一个圆圈。骑士 $2i-1$ 与骑士 $2i$ 坐在同一张课桌。

每名骑士都有一个用整数度量的智力值。记第 $i$ 名骑士的智力值为 $a_i$。Arthur 希望所有课桌的智力总和的最大差异尽可能小。形式化地说，他想要最小化
[ \max_{1 \le i \le n} (a_{2i-1} + a_{2i}) - \min_{1 \le i \le n} (a_{2i-1} + a_{2i})。 ]

然而，骑士守则只允许交换圆桌上相对的骑士，即 Arthur 可以同时执行 $a_i := a_{i+n}$，$a_{i+n} := a_i$，其中 $1 \le i \le n$。Arthur 可以进行任意次这样的交换。他能够获得的最佳结果是多少？

输入

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 1000$）——测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2000$）——课桌的数量。

第二行包含 $2n$ 个整数 $a_1, a_2, \dots, a_{2n}$（$1 \le a_i \le 10^9$）——骑士的智力值。

保证所有测试用例的 $n$ 之和不超过 $2000$。

输出

对于每个测试用例，输出一行一个整数——Arthur 能够达到的最小差值。

样例

输入

5
2
6 6 4 4
1
10 17
3
1 10 1 10 1 10
3
3 3 4 5 5 4
5
1 2 3 4 5 6 7 8 9 10

输出

0
0
0
2
4

说明

在第一个测试用例中，Arthur 可以交换第 $2$ 名骑士和第 $4$ 名骑士。这样每张课桌的智力总和都变为 $10$。

在第三个测试用例中，Arthur 可以进行 $0$ 次操作，此时每张课桌的智力总和均为 $11$。

在第四个测试用例中，Arthur 可以交换第 $2$ 名骑士和第 $5$ 名骑士，得到差值为 $2$。可以证明他无法得到更优的结果。