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$.
