Stock Exchange

You have just started investing in a stock, and an insider told you that there is a list of N prices (in dollars) which will be assigned to that stock over the next N days, in some order that no one knows yet. Each price in that list will be assigned to exactly one of the next N days, and the price within the same day will not change. Your insider friend agreed to do any assignment you want, so you want to assign the prices to the days to maximize your profit.

Suppose you have already assigned the N prices to the N days. Before day 1, you already own 1 unit of that stock and you have no money at all. In each of the following N days, you can either sell (possibly partial units of) some of the stocks you own and receive money in dollars, or buy (possibly partial units of) some of the available stocks and pay in dollars, using the price assigned to that day. You can also do nothing on any given day. Assume that there is an infinite supply of stocks on each day.

Your profit at the end is the amount of money you have, so you need to sell everything by the end of the N days.

Given the list of prices, your task is to arrange them somehow as described above to get the maximum profit.

Your program will be tested on one or more test cases. The first line of the input contains a single integer T (1 ≤ T ≤ 100), the number of test cases. Then T test cases follow.

Each test case starts with a line containing an integer N (1 ≤ N ≤ 105), the number of days, followed by a line containing N positive integers separated by a single space, the list of prices you will assign. Each price is at most 106.

For each test case, print a single line containing a single decimal number rounded to exactly 6 decimal places, the maximum profit you can get. It is guaranteed that the result will not be more than 1018.

In the first test case, you assign the prices in the order '2 1 3'. On the first day you sell the unit you have for 2 dollars, on the second day you buy 2 units for 1 dollar each, and on the third day you sell those 2 units for 3 dollars each, ending up with 6 dollars of profit.

In the second test case, there is just 1 day, so you must sell the unit you have on that day.