408494: GYM103150 H William Tell

H. William Telltime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

There are $$$n$$$ stacks of apples, and the $$$i$$$th stack has $$$a_i$$$ apples.

You can shoot an arrow at any nonempty stack. As a result, the number of apples in the stack undergoes one of the following events with equal probability ($$$50\%$$$ chance):

• The number of apples decreases by $$$1$$$, or
• the number of apples becomes $$$0$$$.

You stop firing arrows when all stacks are empty.

Every time you have a choice of which stack to shoot at, you will always shoot at the stack that minimizes the expected value of the total number of arrows you fire. Find the expected value of the number of arrows you fire (until all stacks are empty).

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of stacks of apples.

The next line of each test case contains $$$n$$$ space-separated integers $$$a_1, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the number of apples in each stack.

The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output one real number — the expected number of arrows you fire.

Your answer will be considered correct if its absolute or relative error doesn't exceed $$$\mathbf{10^{-4}}$$$. Namely, if your answer is $$$a$$$, and the jury's answer is $$$b$$$, then your answer is accepted if and only if $$$\frac{|a-b|}{\max (1,|b|)} \leq 10^{-4}$$$.

ExampleInput

2
4
1 1 1 1
1
2

Output

4.0000
1.5000

Note

In the first test case, no matter which stack you fire at, the resulting number of apples will be $$$0$$$. Therefore, you will always use four arrows.

In the second test case, there is an equal probability of using $$$1$$$ or $$$2$$$ arrows.