A. Meaning Meantime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputPak Chanek has an array $$$a$$$ of $$$n$$$ positive integers. Since he is currently learning how to calculate the floored average of two numbers, he wants to practice it on his array $$$a$$$.While the array $$$a$$$ has at least two elements, Pak Chanek will perform the following three-step operation: Pick two different indices $$$i$$$ and $$$j$$$ ($$$1 \leq i, j \leq |a|$$$; $$$i \neq j$$$), note that $$$|a|$$$ denotes the current size of the array $$$a$$$. Append $$$\lfloor \frac{a_i+a_j}{2} \rfloor$$$$$$^{\text{∗}}$$$ to the end of the array. Remove elements $$$a_i$$$ and $$$a_j$$$ from the array and concatenate the remaining parts of the array. For example, suppose that $$$a=[5,4,3,2,1,1]$$$. If we choose $$$i=1$$$ and $$$j=5$$$, the resulting array will be $$$a=[4,3,2,1,3]$$$. If we choose $$$i=4$$$ and $$$j=3$$$, the resulting array will be $$$a=[5,4,1,1,2]$$$.After all operations, the array will consist of a single element $$$x$$$. Find the maximum possible value of $$$x$$$ if Pak Chanek performs the operations optimally.$$$^{\text{∗}}$$$$$$\lfloor x \rfloor$$$ denotes the floor function of $$$x$$$, which is the greatest integer that is less than or equal to $$$x$$$. For example, $$$\lfloor 6 \rfloor = 6$$$, $$$\lfloor 2.5 \rfloor=2$$$, $$$\lfloor -3.6 \rfloor=-4$$$ and $$$\lfloor \pi \rfloor=3$$$InputEach test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 5000$$$). The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 50$$$) — the length of the array $$$a$$$.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array $$$a$$$.Do note that the sum of $$$n$$$ over all test cases is not bounded.OutputFor each test case, output a single integer: the maximum possible value of $$$x$$$ after all numbers have been picked.ExampleInput351 7 8 4 532 6 555 5 5 5 5Output6
4
5
NoteIn the first test case, the array is initially $$$a=[1,7,8,4,5]$$$. Pak Chanek will perform the following operations: Pick $$$i=1$$$ and $$$j=2$$$, then $$$a=[8,4,5,4]$$$. Pick $$$i=3$$$ and $$$j=2$$$, then $$$a=[8,4,4]$$$. Pick $$$i=2$$$ and $$$j=3$$$, then $$$a=[8,4]$$$. Pick $$$i=1$$$ and $$$j=2$$$, then $$$a=[6]$$$. After all the operations, the array consists of a single element $$$x=6$$$. It can be proven that there is no series of operations that results in $$$x$$$ greater than $$$6$$$ in the end.