Gather on the Clock

Gather on the Clock is a game you play alone.

At the start of a game, several cards are laid out on a ring. Each card has one value written on it.

In one move you pick up any card on the ring and put it on the card that comes next in clockwise order. You gain the absolute difference of the two values as score. The two stacked cards count as a single card from then on, and the value of that card is the value of the card you put on top. You repeat moves until one card is left on the ring, and the score of the game is the sum of the gains.

Write a program that computes the maximum score for a given starting position, which gives the values of the cards and their placement on the ring.

The picture below shows one play. The leftmost drawing is the initial state, and each drawing to the right is the state after one more move. The cards picked up are 1, 3 and 3 in that order, and this game scores 6.

The input consists of several test cases. The first line contains the number of test cases. Each test case is one line. The line starts with the number of cards on the ring, $n$ ($2 \le n \le 100$), followed by the $n$ card values. The values are given in clockwise order. Every value is an integer between 0 and 100, and the numbers are separated by a single space.

For each test case, print the maximum score on one line.