Let me tell you a story of a dangerous prison. There were N prisoners in that prison. It is guaranteed that N is odd. Now each prisoner had a bounty b_i set on his head. The controller (Head Chief) of the prison was a very bad guy. He along with some of his friends (The Mafia Lords) had an idea of playing a game with the lives of the prisoners! The Game was simple; each day randomly two prisoners will be selected (who are alive!) and they will have to fight each other. They must fight until one dies and the sad part is the winning prisoner is also killed by the prison guards as the prison lords don’t want to see the same person fighting another day! The Game ends when there will be exactly one prisoner who will be left alive. The head chief of the prison will set him free and will also give him money equivalent to his bounty as a reward. Now suppose you are one of the prisoners (Ahh sad for you) who wants to know what will be the expected bounty of the prisoner who will be alive at last i.e. when the game ends.

Input

Input starts with an integer T, denoting the number of test cases.

Each test case starts with an integer N which denotes the number of prisoners initially present in the prison. It is guaranteed that n will always be odd. In the next line there will be N space separated integers, where the i^th integer is bⁱ denoting the bounty of the i^th prisoner.

Output

For each case, print the expected bounty of the alive prisoner (when the game ends). Errors less than 10^-6 will be ignored.

Constraints

• 0 ≤ T ≤ 100
• 0 ≤ b_i ≤ 10³
• 1 ≤ N ≤ 10⁵

Example

Input:
3
1
10
3
1 2 3
9
200 933 100 6 20 103 310 1 143

Output:
10.000000000000000
2.0000000000000000
201.77777777777780

Explanation

Explanation for first test case: There is only one prisoner. So the expected value will be 1*10 = 10.

Explanation for second test case: There are three prisoners. On the first game any pair can die out of three possible pairs (1-2), (1-3), (2-3). So the expected value will be (1/3)*1 + (1/3)*2 + (1/3)*3 = 2.

Problem-setter: Imtiaz Shakil Siddique