DreamGrid 和 BaoBao 正在玩一个游戏。游戏中有 $n$ 名士兵，编号从 $1$ 到 $n$。第 $i$ 名士兵的战力值为 $a_i$。DreamGrid 和 BaoBao 打算按照以下规则将士兵分成若干个队伍：

• 一个队伍必须由 $1$ 或 $2$ 名士兵组成。
• 每名士兵必须恰好属于 $1$ 个队伍。
• 如果一个队伍由两名士兵组成（假设为第 $i$ 名和第 $j$ 名士兵），则必须满足 $|i - j| = 1$。

队伍的战力值定义为该队伍所有成员战力值之和。为了公平起见，他们希望在分组后，使最大队伍战力值与最小队伍战力值之间的差值最小。你需要求出这个最小差值。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 10^5$)，表示士兵的人数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$)，其中 $a_i$ 表示第 $i$ 名士兵的战力值。

保证所有测试数据中 $n$ 的总和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示最大队伍战力值与最小队伍战力值之间的最小差值。

样例

输入 1

3
5
-1 4 2 1 1
4
1 3 2 4
1
7

输出 1

1
2
0

说明

我们现在解释第一个样例。所有可能的分组方式如下表所示：

因此答案为 $\min(5, 5, 5, 7, 2, 7, 1, 2) = 1$。