/*This Code is Submitted by billforum for Problem 1249 at 2012-03-18 18:47:08*/#include 
     
      #include 
      
       #include 
       
        using namespace std;const int N=15;const int MAX=100000000;int x[N],m[N][N],d[N][N];void print(int i,int j){        if(i==j) printf("A%d",i);        else if(i
        
         >n)    {                id++;       if(n==0) break;           for(int i=1;i<=n;i++)                   cin>>x[i]>>tmp;                   x[n+1]=tmp;           memset(m,MAX,sizeof(m));           for(int i=1;i<=n;i++)           {                   m[i][i]=0;                   for(int j=i+1;j<=n;j++)                        m[i][j]=MAX;           }           memset(d,0,sizeof(d));                      for(int t=1;t<=n;t++)                   for(int i=1;i<=n-t+1;i++)                   {                           int j=i+t-1;                           for(int k=i;k
         
          (m[i][k]+m[k+1][j]+x[i]*x[k+1]*x[j+1]))                                           {                                                  m[i][j]=(m[i][k]+m[k+1][j]+x[i]*x[k+1]*x[j+1]);                                                   d[i][j]=k;                                             }                           }                   }                                   //cout<
          
           <