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

   04/06/05
                                                                           */

#include<stdio.h>


#define TSIZE 46340

typedef enum
{
   ExprK          = 1,
   ExprProduct    = 2,
   ExprQuotient   = 4,
   ExprSum        = 8,
   ExprDifference = 16

} ExprType;

static struct
{
   ExprType type;
   int length;
   int optimal;
   int a, b;

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


static void PrintExprMask(int n, int mask);

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

static void PutD(char *s, int n)
{
   /*@i1@*/printf(s, n);
}

static void UpdateEntry0(ExprType 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;
      if( Table[x].optimal == TSIZE )
         Optimal[NOptimal++] = x;
      Table[x].optimal = g;
   }
}

static void PrintExpr(int n)
{
   n = (Table[n].type != ExprK)
      ?  (Table[n].type & (ExprProduct|ExprQuotient)) != 0
         ?  PrintExprMask(Table[n].a, ExprK|ExprProduct),
            (
               Table[n].type != ExprProduct
               ? (PutC((int)'/'),
                  (
                     Table[n].b != K
                     ? (PutC((int)'('),
                        PrintExpr(Table[n].b),
                        PutC((int)')'),
                        0)
                     : (PrintExpr(K), 0)
                  ))
               : (PutC((int)'*'),
                  PrintExprMask(Table[n].b, ExprK|ExprProduct|ExprQuotient),
                  0)
            )
         : (PrintExpr(Table[n].a),
            (
               Table[n].type != ExprSum
               ? (PutC((int)'-'),
                  PrintExprMask(Table[n].b, ExprK|ExprProduct|ExprQuotient),
                  0)
               : (PutC((int)'+'),
                  PrintExpr(Table[n].b),
                  0)
            ))
      :  (PutD("%d", K), 0);
}

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

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


int main(int argc, char **argv)
{
   int n;

   if( argc < 2 )
      return printf("%s <number> [...]\n", *argv);

   for(x = 0; *key != '\0'; x += (int)*(key++));
   K = (x % 247) + 3;

   for(i = 0; i < TSIZE; i++)
   {
      Table[i].length = TSIZE;
      Table[i].optimal = TSIZE;
   }

   Table[0].type = ExprDifference;
   Table[K].type = ExprK;

   Table[0].length =
   Table[K].a =
   Table[K].b =
   Table[K].optimal = g = 0;

   Table[0].a =
   Table[0].b =
   Optimal[0] = K;

   Table[0].optimal =
   Table[K].length =
   NOptimal = o = 1;

   for(; NOptimal < TSIZE - 1; o = NOptimal)
   {
      g++;
      for(i = 0; i < o; i++)
      {
         a = Optimal[i];
         for(j = 0; j < o; j++)
         {
            b = Optimal[j];

            if( (x = a * b) < TSIZE )
            {
               UpdateEntry0(ExprProduct);
            }
            if( (a % b) == 0 )
            {
               x = a / b;
               UpdateEntry0(ExprQuotient);
            }
            if( (x = a + b) < TSIZE )
            {
               UpdateEntry0(ExprSum);
            }
            if( (x = a - b) > 1 )
            {
               UpdateEntry0(ExprDifference);
            }
         }
      }
   }


   for(o = 1; o < argc; o++)
   {
      (void)sscanf(*++argv, "%d", &n);
      PutD("%d = ", n);
      PutC(
         (n < 0)
            ? (PutC((int)'-'),
               PutC((int)'('),
               Decompose(-n),
               PutC((int)')'),
               (int)'\n')
            : (Decompose(n),
               (int)'\n'));
   }

   return 0;
}