/* natsumi6.c - Don Yang (uguu.org)

   04/06/05
                                                                           */

#include<stdio.h>


#define TSIZE 46340

#define ExprK           1
#define ExprProduct     2
#define ExprQuotient    4
#define ExprSum         8
#define ExprDifference  16

struct
{
   int type, length, optimal, a, b;
} Table[TSIZE];
int Optimal[TSIZE - 1], NOptimal, K, i, j, a, b, g, x, o, s = TSIZE;
#if 1
   char *key = "`_" "natsumi.c";
#else
   char *key = "`_" "deepthought.c";
#endif


void PutC(int n)
{
   putchar(n);
}

void PutD(char *t, int n)
{
   printf(t, n);
}

void UpdateEntry0(int t)
{
   if( Table[x].length > Table[a].length + Table[b].length )
   {
      Table[x].type = t;
      Table[x].length =
         Table[Table[x].a = a].length + Table[Table[x].b = b].length;
      Table
      [
         Table[x].optimal < s
         ?  x
         :  (Optimal[NOptimal++] = x)
      ].optimal = g;
   }
}

void PrintExpr(int n);

void PrintExprMask(int n, int mask)
{
   n = (Table[n].type & mask)
      ?  (PrintExpr(n), 0)
      :  (PutC(40),
          PrintExpr(n),
          PutC(41),
          0);
}

void PrintExpr(int n)
{
   n = (Table[n].type - ExprK)
      ?  (Table[n].type & (ExprProduct|ExprQuotient))
         ?  PrintExprMask(Table[n].a, ExprK|ExprProduct),
            (
               Table[n].type - ExprProduct
               ? (PutC(47),
                  (
                     Table[n].b - K
                     ? (PutC(40),
                        PrintExpr(Table[n].b),
                        PutC(41),
                        0)
                     : (PrintExpr(K), 0)
                  ))
               : (PutC(42),
                  PrintExprMask(Table[n].b, ExprK|ExprProduct|ExprQuotient),
                  0)
            )
         : (PrintExpr(Table[n].a),
            (
               Table[n].type - ExprSum
               ? (PutC(45),
                  PrintExprMask(Table[n].b, ExprK|ExprProduct|ExprQuotient),
                  0)
               : (PutC(43),
                  PrintExpr(Table[n].b),
                  0)
            ))
      :  (PutD("%d", K), 0);
}

void Decompose(int n)
{
   if( n < s )
   {
      PrintExpr(n);
   }
   else if( n > (s - 1) * (s - 1) )
   {
      PutD("%d*(", K);
      Decompose(n / K);
      PutC(41);
      if( n % K )
      {
         PutC(43);
         PutC(40);
         PrintExpr(n % K);
         PutC(41);
      }
   }
   else
   {
      a = n;
      b = 0;
      for(i = 2; i <= (j = n / i); i++)
      {
         if( j < s )
         {
            if( a > (g = Table[i].length + Table[j].length +
                         Table[n % i].length) )
            {
               a = g;
               b = i;
            }
         }
      }
      PrintExprMask(b, ExprK|ExprProduct);
      PutC(42);
      PrintExprMask(n / b, ExprK|ExprProduct|ExprQuotient);
      if( n % b )
      {
         PutC(43);
         PrintExpr(n % b);
      }
   }
}


int main(int argc, char **argv)
{
   if( argc > 1 )
   {

      for(x = i = 0; *key; x += (int)*(key++));

      for(K = (x % 247) + 3; i < s; i++)
      {
         Table[i].length = s;
         Table[i].optimal = s;
      }

      Table
      [
         Table[0].length =
         Table[K].a =
         Table[K].b =
         Table[K].optimal = g = 0
      ].type = ExprDifference;
      Table[
         Table[0].a =
         Table[0].b =
         Optimal[0] = K
      ].type = ExprK;


      for(Table[0].optimal = Table[K].length = NOptimal = o = 1;
          NOptimal < s - 1;
          o = NOptimal)
      {
         g++;
         for(i = 0; i < o;)
         {
            a = Optimal[i++];
            for(j = 0; j < o;)
            {
               if( (x = a * (b = Optimal[j++])) < s )
                  UpdateEntry0(ExprProduct);
               if( !(a % b) )
               {
                  x = a / b;
                  UpdateEntry0(ExprQuotient);
               }
               if( (x = a + b) < s )
                  UpdateEntry0(ExprSum);
               if( (x = a - b) > 1 )
                  UpdateEntry0(ExprDifference);
            }
         }
      }


      for(o = 1;
          o++ < argc;
          PutC(
             (g < 0)
                ? (PutC(45),
                   PutC(40),
                   Decompose(-g),
                   PutC(41),
                   10)
                : (Decompose(g),
                   10)))
      {
         sscanf(*++argv, "%d", &g);
         PutD("%d = ", g);
      }

   }
   return 0;
}