시계 위에 모으기

시계 위에 모으기는 혼자서 하는 게임이다.

게임을 시작할 때 고리 위에 카드 여러 장을 늘어놓는다. 카드마다 값이 하나씩 적혀 있다.

한 번의 이동에서는 고리 위의 카드 하나를 집어서 시계 방향으로 바로 다음에 있는 카드 위에 올려놓는다. 이때 두 카드에 적힌 값의 차이의 절댓값만큼 점수를 얻는다. 겹쳐진 두 카드는 이후 한 장의 카드로 취급하고, 그 카드의 값은 위에 올려놓은 카드의 값이다. 고리에 카드가 한 장만 남을 때까지 이동을 반복하며, 얻은 점수를 모두 더한 값이 그 게임의 점수가 된다.

카드의 값과 고리 위의 배치가 주어질 때 얻을 수 있는 최대 점수를 구하는 프로그램을 작성하라.

아래 그림은 게임이 진행되는 한 가지 예다. 맨 왼쪽이 처음 상태이고, 오른쪽으로 갈수록 이동을 한 번씩 더 진행한 상태다. 집어 올린 카드는 차례로 1, 3, 3이고 이 게임의 점수는 6이다.

입력은 테스트 케이스 여러 개로 이루어진다. 첫 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한 줄로 주어진다. 그 줄은 고리 위에 놓인 카드의 개수 $n$ ($2 \le n \le 100$)으로 시작하고, 뒤이어 카드의 값 $n$개가 온다. 값은 시계 방향 순서로 주어진다. 모든 값은 0 이상 100 이하의 정수이고, 각 수는 공백 하나로 구분된다.

각 테스트 케이스마다 얻을 수 있는 최대 점수를 한 줄에 출력한다.