Evil Doctor D has captured Hulk and put him into an underground tunnel system. The tunnel system is closed but sadly Hulk is not aware of this fact. 

Tunnel structure is of the form of an asterisk. There are many tunnels coming out of single center point. Hulk is left unconscious at the outer end of tunnel. Once Hulk gets up he just wants to get out of this underground system. Since its completely dark down there, Hulk adopts the following strategy : He runs to get to the center and once he gets there he randomly enters another tunnel other than the one he came from. He will run to outer end of this tunnel, come back to center and again choose a random tunnel other than presently exited one (may as well be the first chosen one). 

Note: The starting point of Hulk is at the end of the tunnel whose length is mentioned first in the array

You have to find out the the expected length of Hulk's path in which he would have visited the ends of all tunnels at least once.

Input

First line contains integer n giving number of test cases. 

n test cases follow. 

For each test case contains k followed k space separated integers representing the lengths of the k tunnels.

Output

One line per test case containing one number E which is the expected length of Hulk's path.

Constraints

2 <= k <= 50

Each integer a[i] : 1 <= a[i] <= 10^5

Example

Input:
2
2 40 40
3 50 50 50

Output:
80.0
300.0

In test case 1 there are two tunnels of length 40 each meeting at the center. Hulk runs from end of first to center. He will take the second on to reach the end of second. Hence 40 + 40 = 80.

In test case 2 there are three tunnels of length 50 each meeting at the center. Hulk would run from end of 0th tunnel to center (Total: 50). Run to end of one of the other two tunnels and back to center (Total: 50 + 50*2).  Now to cover last tunnel remaining, he either choose the third tunnel immediately with probability 1/2 or chooses the first, goes to end, comes back to center and chooses third with probability 1/2 * 1/2 and so on. Total expected path length = 150 + 50 * 1/2 + 150 * 1/2 * 1/2 + 250 * (1/2)^3 ... = 300.0