Sequence Merging

You are given a sequence $a_1, a_2, \dots, a_n$. In one step you can pick two adjacent numbers $a_i$ and $a_{i+1}$ and replace both of them with the single number $\max(a_i, a_{i+1})$. That step costs $\max(a_i, a_{i+1})$. Each step makes the sequence one shorter, so after $n-1$ steps a single number is left.

Given the sequence, compute the minimum total cost of reducing it to length 1.

The first line contains the number of test cases $T$ ($1 \le T \le 100000$).

Each test case takes two lines. The first line contains the length of the sequence $N$ ($2 \le N \le 5000$). The second line contains the $N$ integers of the sequence, separated by single spaces. Every integer is between $1$ and $100000$ inclusive.

For each test case, print one line in the format Case #x: R, where $x$ is the test case number starting from 1 and $R$ is the minimum cost of reducing that sequence to length 1.