human
Write me a Python program to print a single value — the maximum value that Ezzat can achieve given the following:
Ezzat has an array of n integers (maybe negative). He wants to split it into two non-empty subsequences a and b, such that every element from the array belongs to exactly one subsequence, and the value of f(a) + f(b) is the maximum possible value, where f(x) is the average of the subsequence x. 

A sequence x is a subsequence of a sequence y if x can be obtained from y by deletion of several (possibly, zero or all) elements.

The average of a subsequence is the sum of the numbers of this subsequence divided by the size of the subsequence.

For example, the average of [1,5,6] is (1+5+6)/3 = 12/3 = 4, so f([1,5,6]) = 4.

Input

The first line contains a single integer t (1 ≤ t ≤ 10^3)— the number of test cases. Each test case consists of two lines.

The first line contains a single integer n (2 ≤ n ≤ 10^5).

The second line contains n integers a_1, a_2, …, a_n (-10^9 ≤ a_i ≤ 10^9).

It is guaranteed that the sum of n over all test cases does not exceed 3⋅10^5.

Output

For each test case, print a single value — the maximum value that Ezzat can achieve.

Your answer is considered correct if its absolute or relative error does not exceed 10^{-6}.

Formally, let your answer be a, and the jury's answer be b. Your answer is accepted if and only if \frac{|a - b|}{max{(1, |b|)}} ≤ 10^{-6}.

Example

Input

4
3
3 1 2
3
-7 -6 -6
3
2 2 2
4
17 3 5 -3

Output

4.500000000
-12.500000000
4.000000000
18.666666667

Note

In the first test case, the array is [3, 1, 2]. These are all the possible ways to split this array: 

  * a = [3], b = [1,2], so the value of f(a) + f(b) = 3 + 1.5 = 4.5. 
  * a = [3,1], b = [2], so the value of f(a) + f(b) = 2 + 2 = 4. 
  * a = [3,2], b = [1], so the value of f(a) + f(b) = 2.5 + 1 = 3.5. 

Therefore, the maximum possible value 4.5.

In the second test case, the array is [-7, -6, -6]. These are all the possible ways to split this array: 

  * a = [-7], b = [-6,-6], so the value of f(a) + f(b) = (-7) + (-6) = -13. 
  * a = [-7,-6], b = [-6], so the value of f(a) + f(b) = (-6.5) + (-6) =...
Solve the task in PYTHON3.
assistant
#Here is Python program to print a single value — the maximum value that Ezzat can achieve.

# DEFINING SOME GOOD STUFF
import heapq
import sys
from math import *
import threading
from heapq import *
from itertools import count
from pprint import pprint
from collections import defaultdict
from heapq import heapify, heappop, heappush

# threading.stack_size(10**8)
# sys.setrecursionlimit(300000)
'''
-> if you are increasing recursionlimit then remember submitting using python3 rather pypy3
-> sometimes increasing stack size don't work locally but it will work on CF
'''

mod = 10 ** 9+7
inf = 10 ** 15
decision = ['NO', 'YES']
yes = 'YES'
no = 'NO'

# ------------------------------FASTIO----------------------------
import os

from io import BytesIO, IOBase

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n")+(not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)

class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s:...