A. Gourmand

众所周知 Kimo·Gourmand·Yami 一天吃四顿饭。

Yami 每次吃饭时会从他的菜谱中随机选择一个菜肴进行品尝。

Yami 的菜谱中有 $n(2\nmid n)$ 种不同的菜肴，第 $i$ 种菜肴的热量为 $a_i$(卡路里)，不同菜肴的热可能相同。

假设 Yami 在四顿饭中吃的菜肴的编号分别为 $i,j,k,l(1 \leq i,j,k,l\leq n)$，显然 Yami 在一天中会有 $n^4$ 种不同的解决四顿饭的方式，他想要知道在这 $n^4$ 种不同的方式中，每天摄入的热量的中位数是什么?

即请求出对于所有的 $i,j,k,l(1 \leq i,j,k,l\leq n)$ 我们对 $a_i+a_j+a_k+a_l$ 从小到大排序后第 $\lceil {n^4 \over 2} \rceil$ 个数是什么？(关于中位数的定义以本句为准)

第一行一个正整数 $T(1\leq T \leq 10)$ 代表测试数据组数。

每组测试数据第一行一个正整数 $n(1 \leq n \leq 399\wedge 2\nmid n)$。

下面一行 $n$ 个正整数 $a_1,a_2,\ldots,a_n(1 \leq a_i \leq 2 \times 10^{18})$。

共 $T$ 行，每行一个正整数代表 Yami 每天摄入的热量的中位数。

样例输入

2
3
1 2 3
3
8 10000000000000 16245

样例输出

8
10000000032498