Optimal Array Multiplication Sequence

Given two arrays $A$ and $B$, we can determine the array $C = A \times B$ using the standard definition of matrix multiplication:

$C_{i,j} = \sum_{k} A_{i,k} \times B_{k,j}$

For this product to be defined, the number of columns in $A$ must equal the number of rows in $B$. Let $\text{rows}(A)$ and $\text{cols}(A)$ denote the number of rows and columns of $A$, respectively. The result $C$ has the same number of rows as $A$ and the same number of columns as $B$, and the number of scalar multiplications needed to compute all of $C$ is

$\text{rows}(A) \times \text{cols}(B) \times \text{cols}(A).$

For example, if $A$ is a $10 \times 20$ array and $B$ is a $20 \times 15$ array, it takes $10 \times 15 \times 20 = 3000$ multiplications to compute $C$.

To multiply more than two arrays we may choose how to proceed. For instance, the product $X \times Y \times Z$ can be computed as $(X \times Y) \times Z$ or as $X \times (Y \times Z)$. Suppose $X$ is $5 \times 10$, $Y$ is $10 \times 20$, and $Z$ is $20 \times 35$. The two orders require different numbers of multiplications:

The order clearly affects how many multiplications are required. Given the size of each array in a sequence of arrays to be multiplied, determine the minimum possible number of scalar multiplications over all valid orders of computing the product.

The input consists of several test cases. Each test case begins with an integer $N$, the number of arrays to be multiplied, followed by $N$ pairs of integers giving the number of rows and columns of each array, in the same order in which the arrays are to be multiplied. $N$ is no larger than $10$. A value of $0$ for $N$ indicates the end of the input. Adjacent arrays are always dimensioned so that their product is defined.

For each test case, output on a single line the minimum number of scalar multiplications needed to compute the product of all the arrays. Prefix each line with the case number in the form Case X: , numbered sequentially starting from $1$.