Pak Chanek 有一个包含 $$$n$$$ 正整数的数组 $$$a$$$。由于他目前正在学习如何计算两个数字的下限平均值,因此他想在数组 $$$a$$$ 上进行练习。
虽然数组 $$$a$$$ 至少有两个元素,Pak Chanek 将执行以下三步操作:
1. 选择两个不同的索引 $$$i$$$ 和 $$$j$$$ ($$$1 \leq i, j \leq |a|$$$; $$$i \neq j$$$),注意 $$$|a|$$$ 表示数组 $$$a$$$ 的当前大小。
2. 将 $$$\lfloor \frac{a_i+a_j}{2} \rfloor$$$$$$^{\text{*}}$$$ 附加到数组末尾。
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$$$ 的最大可能值。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 5000$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 50$$$) — 数组 $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。
请注意,所有测试用例的 $$$n$$$ 之和是没有界限的。
输出
对于每个测试用例,输出一个整数:选择所有数字后 $$$x$$$ 的最大可能值。
示例
输入 #1
3 5 1 7 8 4 5 3 2 6 5 5 5 5 5 5 5
输出 #1
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$$$。