Statement

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:

1. 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$ .
2. Append $\lfloor \frac{a_i+a_j}{2} \rfloor$ $^{\text{∗}}$ to the end of the array.
3. 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$

Format

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.

Sample

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

6
4
5