Pak 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$$$

Input

Each 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.

Output

For each test case, output a single integer: the maximum possible value of $$$x$$$ after all numbers have been picked.

Note

In 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.

Meaning Mean

Examples