Repairman

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 3024
64-bit integer IO format: %I64d      Java class name: Main

Description

The traveling repairman problem (TRP) is classical NP-Hard problem, which is also known as minimum latency problem (MLP) and delivery man problem. Suppose that we have a graph with n nodes, in each one there is a machine that has to be repaired, and there is only one repairman. We are given the time required by the repairman to travel among nodes. The objective is to find a tour that minimizes the total waiting time of all the machines. (ignore time of repairing)

Now for simplicity, we place all nodes on a straight line. Your task is to find out smallest sum of waiting time of all the machines.

Input

The first line of input contains a single integer T, which is the number of test case. Each case starts with a line containing a single integer N (1 ≤ N ≤ 400), the number of nodes. The next line gives a list of N corrdinate of nodes. Each corrdinate is a integer in the range [-1000, 1000]. Consecutive integers are separated by a single space charcter. The repairman will depart from origin. Suppose he travels at unit speed.

Output

For each case, output one line with the smallest sum of waiting time.

Sample Input

2
2
-1 2
3
-1 1 2

Sample Output

5
8

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .