A. 平均值的意义
每个测试点时间限制：$1$ 秒
内存限制：$256$ 兆字节

Pak Chanek 有一个由 $n$ 个正整数组成的数组 $a$。因为他正在学习如何计算两个数的向下取整平均值，所以他想在自己的数组 $a$ 上练习这个操作。

当数组 $a$ 至少有两个元素时，Pak Chanek 会执行以下三步操作：

1. 选择两个不同的下标 $i$ 和 $j$（$1 \le i, j \le |a|$，$i \neq j$），其中 $|a|$ 表示数组 $a$ 当前的元素个数。
2. 将 $\left\lfloor \frac{a_i + a_j}{2} \right\rfloor$ 追加到数组的末尾。
3. 从数组中删除元素 $a_i$ 和 $a_j$，并将剩余部分拼接起来。

例如，假设 $a = [5, 4, 3, 2, 1, 1]$。

• 如果选择 $i = 1$ 和 $j = 5$，结果数组为 $a = [4, 3, 2, 1, 3]$。
• 如果选择 $i = 4$ 和 $j = 3$，结果数组为 $a = [5, 4, 1, 1, 2]$。

所有操作结束后，数组将只剩下一个元素 $x$。如果 Pak Chanek 以最优方式执行操作，求出 $x$ 的最大可能值。

$\lfloor x \rfloor$ 表示对 $x$ 向下取整，即小于或等于 $x$ 的最大整数。
例如：$\lfloor 6 \rfloor = 6$，$\lfloor 2.5 \rfloor = 2$，$\lfloor -3.6 \rfloor = -4$，$\lfloor \pi \rfloor = 3$。

输入格式

每个测试点包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 5000$），表示测试用例的数量。

接下来每个测试用例的格式如下：

• 第一行包含一个整数 $n$（$2 \le n \le 50$），表示数组 $a$ 的长度。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示数组 $a$ 的元素。

注意：所有测试用例的 $n$ 之和没有限制。

输出格式

对于每个测试用例，输出一个整数：在所有数都被选取后，最终单个元素 $x$ 的最大可能值。

示例

输入

3
5
1 7 8 4 5
3
2 6 5
5
5 5 5 5 5

输出

6
4
5

示例解释

第一个测试用例：初始数组 $a = [1, 7, 8, 4, 5]$。
Pak Chanek 执行以下操作：

1. 选择 $i = 1$ 和 $j = 2$，得到 $a = [8, 4, 5, 4]$。
2. 选择 $i = 3$ 和 $j = 2$，得到 $a = [8, 4, 4]$。
3. 选择 $i = 2$ 和 $j = 3$，得到 $a = [8, 4]$。
4. 选择 $i = 1$ 和 $j = 2$，得到 $a = [6]$。

最终 $x = 6$。可以证明，不存在任何操作序列能使最终的 $x$ 大于 $6$。