역기 정렬하기

건강대학교 체력단련장에는 무게가 모두 다른 역기 $N$ 개가 고정대 위에 하나씩 놓여 있다. 아침에는 이용자의 편의를 위해 아래 그림처럼 가벼운 역기부터 무거운 역기 순으로 정렬해 둔다. (그림은 $N$ 이 5 인 경우)

하지만 체력단련장이 문을 닫을 때가 되면 역기 $N$ 개는 무게 순서와 상관없이 어지럽게 놓여 있다. 다음이 그러한 예 중 하나이다.

체력단련장 관리자인 현우는 문을 닫으면서 어지럽게 놓인 역기 $N$ 개를 무게의 오름차순으로 정렬하는 일을 맡고 있다. 역기의 무게가 만만치 않기 때문에 현우는 들어 옮기는 역기 무게의 합을 최소로 하여 정렬하고자 한다. 안전을 위해 현우는 한 번에 두 개의 역기를 들어 옮기지 않는다. 역기를 들어 옮기는 방법은 다음 세 가지다.

• 고정대에 놓인 역기를 체력단련장 바닥에 내려놓는다.
• 고정대에 놓인 역기를 빈 고정대로 옮긴다.
• 체력단련장 바닥에 놓인 역기를 빈 고정대로 옮긴다.

역기를 한 번 들어 옮길 때마다 그 역기의 무게가 합에 더해진다. 예를 들어 역기 세 개가 고정대 위에 차례로 5kg, 4kg, 1kg 순으로 놓여 있다고 하자. 다음 순서로 정렬하면 옮긴 역기 무게의 합은 7kg 이 된다. 먼저 1kg 역기를 체력단련장 바닥으로 옮기고, 1kg 역기가 놓여 있던 빈 고정대 위로 5kg 역기를 옮긴다. 마지막으로 바닥에 내려놓았던 1kg 역기를 처음에 5kg 역기가 놓여 있던 고정대로 옮긴다.

표준 입력으로 입력받는다. 입력은 $T$ ($1 \le T \le 10$) 개의 테스트 케이스로 이루어진다. 첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 각 테스트 케이스는 두 줄이다. 첫 줄에 역기의 개수 $N$ 이 1,000 이하의 양의 정수로 주어지고, 둘째 줄에 역기 $N$ 개의 무게가 고정대에 놓인 순서대로 주어진다. 역기의 무게는 서로 다르다.

표준 출력으로 출력한다. 각 테스트 케이스마다 역기를 무게의 오름차순으로 정렬하기 위해 옮겨야 하는 무게 합의 최솟값을 한 줄에 하나씩 출력한다.