你刚刚开始投资股票，一位内部人士告诉你，未来 $N$ 天内将会有 $N$ 个价格（以美元为单位）分配给该股票（分配顺序未知）。列表中的每个价格都将恰好分配给未来 $N$ 天中的某一天，且同一天内的价格不会改变。你的这位内部人士朋友愿意为你做任何分配，因此你希望通过分配这些价格来最大化你的利润。

假设你已经将 $N$ 个价格分配给了 $N$ 天。在第 1 天之前，你已经拥有 1 单位的该股票，且手头没有任何现金。在接下来的 $N$ 天里，每一天你都可以卖出（可以是部分单位）你拥有的股票（你会获得美元），或者买入（可以是部分单位）可用的股票（你需要支付美元），交易价格为当天分配的价格。你也可以在任何一天什么都不做。假设每一天都有无限的股票供应。

最终的利润就是你拥有的现金总额，因此你需要在 $N$ 天结束时卖出所有股票。

给定价格列表，你的任务是进行某种分配，以获得最大利润。

输入格式

程序将在一个或多个测试用例上进行测试。输入的第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。接下来是 $T$ 个测试用例。

每个测试用例以一行包含一个整数 $N$ ($1 \le N \le 10^5$) 开始，表示天数；随后是一行包含 $N$ 个正整数，由空格分隔，表示你将要分配的价格列表，每个价格最大为 $10^6$。

输出格式

对于每个测试用例，输出一行，包含一个保留到小数点后 6 位的十进制数，表示你能获得的最大利润。保证结果不会超过 $10^{18}$。

样例

样例输入 1

2
3
1 2 3
1
100

样例输出 1

6.000000
100.000000

说明

在第一个测试用例中，你将价格按“2 1 3”的顺序分配，第一天你以 2 美元卖出你拥有的单位，第二天你以 1 美元买入 2 个单位，第三天你以 3 美元卖出这 2 个单位，最终你获得了 6 美元的利润。

在第二个测试用例中，你只有 1 天时间，你必须在那一天卖出你拥有的单位。