#include <stdio.h>#include <iostream>#define MAX 11using namespace std;int dp[MAX][MAX],path[MAX][MAX],data[MAX];int n;void Init(){ int i=0,j=1,m=n; while(m--) { scanf("%d%d",&data[i],&data[j]); i++; j++; }}void MatrixChain(){ int i,j,k,r; for(i=1;i<=n;i++) dp[i][i]=0; for(r=2;r<=n;r++) for(i=1;i<=n-r+1;i++) { j=i+r-1; dp[i][j]=dp[i][i]+dp[i+1][j]+data[i-1]*data[i]*data[j]; path[i][j]=i; for(k=i+1;k<j;k++) { int temp=dp[i][k]+dp[k+1][j]+data[i-1]*data[k]*data[j]; if(temp<dp[i][j]) { dp[i][j]=temp; path[i][j]=k; } } }}void TraceBack(int i,int j){ if(i==j) { cout<<"A"<<i; } else if(i==j-1) { cout<<"A"<<i<<" x A"<<j; } else { if(i!=path[i][j]) cout << "("; TraceBack(i,path[i][j]); if (i!=path[i][j]) cout<<") x "; else cout<<" x "; if (path[i][j]+1!=j) cout<<"("; TraceBack(path[i][j]+1,j); if (path[i][j]+1!=j) cout << ")"; }}int main(){ int zz=1; while(scanf("%d",&n)!=EOF&&n!=0) { Init(); MatrixChain(); printf("Case %d: (",zz++); TraceBack(1,n); printf(")n"); } return 0;}
