Expected Cost

Time Limit: 3 Seconds    Memory Limit: 65536 KB

Bahareh is a good ACM competitor of RazShahr University. Her coach has found out that she may go to Shiraz University in the next year. He has N independent programs to improve her skills. A non-empty subset of these programs will be finally chosen with a special permutation to achieve a perfect effect. For example by having 2 programs {A, B}, there are four different program-lists: [A], [B], [A, B], [B, A]. Also, for three programs {A, B ,C} there are 15 program-lists.

Each program has an independent cost. Due to that Bahareh may be not the student of this university in the next regional competition, the coach wants to measure the expectation of the total cost of training Bahareh. If the costs of A and B in the former example is 4 and 6, respectively; the candidate lists have costs equal to 4, 6, 10 and 10, with the same order. Therefore, the total cost is expected to be 7.5.


There are T<100 test-cases. T is given at the first line. Afterwards, each test-case is presented one by one, each one in two lines. The first line contains a positive integer N≤20 as the number of programs. The second line contains N integers as the cost of the programs.


For each test-case, print in a separate line, the expected total cost with six digits after decimal point.

Sample Input

4  6
1  2  3

Sample Output


Source: 13th Iran Nationwide Internet Contest - Shiraz