There is a number sequence A1,A2,...,An. Let f(i)=min{|Aj-Ai| ,j<i}. You only need to compute f(1)+f(2)+...+f(n).
Input
The first line is an integer c which shows the number of cases. For each case there is a single line. The first number is n and the next n positive integer is A1 to An. (n<10000, Ai<100000)

Output

For each case print the answer at a single line.

Sample Input
2
3 1 2 3
4 2 3 1 4

Sample Output
2
3
我只有暴力直接算的思路，因此总是超时。不知道各位大神有什么想法，这题可以用动态规划解吗？