NanoApe Loves Sequence

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 262144/131072 K (Java/Others)

Description

NanoApe, the Retired Dog, has returned back to prepare for the National Higher Education Entrance Examination!

In math class, NanoApe picked up sequences once again. He wrote down a sequence with $n$ numbers on the paper and then randomly deleted a number in the sequence. After that, he calculated the maximum absolute value of the difference of each two adjacent remained numbers, denoted as $F$.

Now he wants to know the expected value of $F$, if he deleted each number with equal probability.

Input

The first line of the input contains an integer $T$, denoting the number of test cases.

In each test case, the first line of the input contains an integer $n$, denoting the length of the original sequence.

The second line of the input contains $n$ integers $A_1, A_2, ..., A_n$, denoting the elements of the sequence.

$1 \le T \le 10,~3 \le n \le 100000,~1 \le A_i \le 10^9$

Output

For each test case, print a line with one integer, denoting the answer.

In order to prevent using float number, you should print the answer multiplied by $n$.

Sample Input

1 4 1 2 3 4

Sample Output

6

Hint

wange2014

Source

BestCoder Round #86

提交代码