최적의 행렬 곱셈 순서

문제

두 행렬 $A$와 $B$가 있을 때, 행렬 곱셈의 표준 정의에 따라 곱 $C = A \times B$의 각 원소는 다음과 같이 정해진다.

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

이 곱이 정의되려면 $A$의 열 개수와 $B$의 행 개수가 같아야 한다. 행렬 $A$의 행 개수와 열 개수를 각각 $\text{rows}(A)$, $\text{cols}(A)$로 표기하자. 결과 행렬 $C$는 $A$와 같은 수의 행, $B$와 같은 수의 열을 가지며, $C$ 전체를 계산하는 데 필요한 스칼라 곱셈의 횟수는

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

이다. 예를 들어 $A$가 $10 \times 20$ 행렬이고 $B$가 $20 \times 15$ 행렬이면, $C$를 구하는 데 $10 \times 15 \times 20 = 3000$번의 곱셈이 필요하다.

세 개 이상의 행렬을 곱할 때에는 계산 순서를 선택할 수 있다. 예컨대 세 행렬 $X, Y, Z$의 곱 $X \times Y \times Z$는 $(X \times Y) \times Z$로 계산할 수도 있고 $X \times (Y \times Z)$로 계산할 수도 있다. $X$가 $5 \times 10$, $Y$가 $10 \times 20$, $Z$가 $20 \times 35$ 행렬일 때 두 방식에 필요한 곱셈 횟수를 비교하면 다음과 같다.

$(X \times Y) \times Z$	$X \times (Y \times Z)$
$X \times Y$: $5 \times 20 \times 10 = 1000$번 (결과는 $5 \times 20$)	$Y \times Z$: $10 \times 35 \times 20 = 7000$번 (결과는 $10 \times 35$)
이어서 $5 \times 35 \times 20 = 3500$번	이어서 $5 \times 35 \times 10 = 1750$번
합계: $4500$번	합계: $8750$번

이처럼 계산 순서에 따라 필요한 곱셈 횟수가 달라진다. 곱해야 할 행렬들의 크기가 순서대로 주어질 때, 필요한 스칼라 곱셈 횟수가 최소가 되도록 계산 순서를 택했을 때의 그 최소 곱셈 횟수를 구하여라.

입력

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 곱할 행렬의 개수를 나타내는 정수 $N$으로 시작하고, 이어서 $N$개의 정수 쌍이 주어진다. 각 쌍은 한 행렬의 행 개수와 열 개수를 나타내며, 주어지는 순서는 행렬을 곱하는 순서와 같다. $N$은 $10$을 넘지 않는다. $N$이 $0$이면 입력의 끝을 의미한다. 인접한 두 행렬은 항상 곱셈이 가능하도록 크기가 맞추어져 주어진다.

출력

각 테스트 케이스마다, 모든 행렬을 곱하는 데 필요한 스칼라 곱셈 횟수의 최솟값을 한 줄에 출력한다. 각 줄 앞에는 Case X: 형식으로 케이스 번호를 붙이며, 번호는 $1$부터 차례대로 매긴다.