E2. 让我给你上一课（困难版）
每个测试点的时间限制：2秒
每个测试点的内存限制：256兆字节

这是某道题的困难版本。简单版本与困难版本唯一的区别在于对 $t$ 和 $n$ 的约束不同。只有当你解决了两个版本时，才可以进行 Hack。

亚瑟正在给他著名的 $2n$ 名骑士上课。像其他学生一样，他们两人一桌坐着，但出于习惯，他们围成一个圆圈。编号为 $2i-1$ 的骑士与编号为 $2i$ 的骑士坐在同一桌。

每位骑士都有一个可以量化为整数的智力值。用 $a_i$ 表示第 $i$ 位骑士的智力值。亚瑟希望所有桌子的智力总和的最大差异尽可能小。形式化地说，他希望最小化

$$\max_{1 \le i \le n} (a_{2i-1}+a_{2i}) - \min_{1 \le i \le n} (a_{2i-1}+a_{2i}). $$

然而，骑士法典只允许交换圆桌上相对位置的骑士，即亚瑟可以同时执行 $a_i := a_{i+n}$，$a_{i+n} := a_i$ 对于任意 $1 \le i \le n$。亚瑟可以进行任意多次这样的交换。他能达到的最佳结果是多少？

输入
每个测试包含多个测试用例。第一行是一个整数 $t$（$1 \le t \le 10000$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行是一个整数 $n$（$1 \le n \le 100000$），表示桌子的数量。

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

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

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

样例
输入

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

注释
在第一个测试用例中，亚瑟可以交换第 $2$ 位和第 $4$ 位骑士。那么每张桌子的智力总和都变成了 $10$。

在第三个测试用例中，亚瑟可以进行 $0$ 次操作，这样每张桌子的智力总和都是 $11$。

在第四个测试用例中，亚瑟可以交换第 $2$ 位和第 $5$ 位骑士，使得差值变为 $2$。可以证明他无法得到比这更好的结果。