Problem G: Gather on the Clock

There is a self-playing game called Gather on the Clock.

At the beginning of a game, a number of cards are placed on a ring. Each card is labeled by a value.

In each step of a game, you pick up any one of the cards on the ring and put it on the next one in clockwise order. You will gain the score by the difference of the two values. You should deal with the two cards as one card in the later steps. You repeat this step until only one card is left on the ring, and the score of the game is the sum of the gained scores.

Your task is to write a program that calculates the maximum score for the given initial state, which specifies the values of cards and their placements on the ring.

The figure shown below is an example, in which the initial state is illustrated on the left, and the subsequent states to the right. The picked cards are 1, 3 and 3, respectively, and the score of this game is 6.

Figure 6: An illustrative play of Gather on the Clock

Input

The input consists of multiple test cases. The first line contains the number of cases. For each case, a line describing a state follows. The line begins with an integer n (2 ≤ n ≤ 100), the number of cards on the ring, and then n numbers describing the values of the cards follow. Note that the values are given in clockwise order. You can assume all these numbers are non-negative and do not exceed 100. They are separated by a single space character.

Output

For each case, output the maximum score in a line.

Sample Input

2
4 0 1 2 3
6 1 8 0 3 5 9

Output for the Sample Input

6
34

---