수열 합치기

수열 $a_1, a_2, \dots, a_n$이 주어진다. 한 번의 연산에서 인접한 두 수 $a_i$와 $a_{i+1}$을 골라 그 두 수를 $\max(a_i, a_{i+1})$ 하나로 바꿀 수 있고, 이때 드는 비용은 $\max(a_i, a_{i+1})$이다. 연산을 한 번 하면 수열의 길이가 1 줄어들므로 $n-1$번 하면 길이가 1이 된다.

수열이 주어졌을 때, 길이 1로 만드는 데 드는 최소 비용을 구하는 프로그램을 작성하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 100000$)

각 테스트 케이스는 두 줄이다. 첫째 줄에 수열의 길이 $N$이 주어진다. ($2 \le N \le 5000$) 둘째 줄에 수열을 이루는 $N$개의 정수가 공백 한 개로 구분되어 주어진다. 각 정수는 $1$ 이상 $100000$ 이하다.

각 테스트 케이스마다 한 줄에 Case #x: R 형식으로 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $R$은 그 수열을 길이 1로 만드는 최소 비용이다.