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

   04/06/05
                                                                           */

#include<stdio.h>
#include<stdlib.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].a = a;
      Table[x].b = b;
      Table[x].length = Table[a].length + Table[b].length;
      if( Table[x].optimal == TSIZE )
         Optimal[NOptimal++] = x;
      Table[x].optimal = g;
   }
}

static void PrintExpr(int n)
{
   switch( Table[n].type )
   {
      case ExprSum:
         PrintExpr(Table[n].a);
         PutC((int)'+');
         PrintExpr(Table[n].b);
         break;
      case ExprDifference:
         PrintExpr(Table[n].a);
         PutC((int)'-');
         PrintExprMask(Table[n].b, ExprK|ExprProduct|ExprQuotient);
         break;
      case ExprProduct:
         PrintExprMask(Table[n].a, ExprK|ExprProduct);
         PutC((int)'*');
         PrintExprMask(Table[n].b, ExprK|ExprProduct|ExprQuotient);
         break;
      case ExprQuotient:
         PrintExprMask(Table[n].a, ExprK|ExprProduct);
         PutC((int)'/');
         if( Table[n].b != K )
         {
            PutC((int)'(');
            PrintExpr(Table[n].b);
            PutC((int)')');
         }
         else
         {
            PrintExpr(K);
         }
         break;
      case ExprK:
         PutD("%d", K);
         break;
      default:
         break;
   }
}

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

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 )
            continue;
         if( a > Table[i].length + Table[j].length + Table[n % i].length )
         {
            a = Table[i].length + Table[j].length + Table[n % i].length;
            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);

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

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

   Table[0].type = ExprDifference;
   Table[0].length = 0;
   Table[0].a = K;
   Table[0].b = K;
   Table[0].optimal = 1;

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

   do
   {
      g++;
      for(i = 0; i < o; i++)
      {
         a = Optimal[i];
         for(j = 0; j < o; j++)
         {
            b = Optimal[j];

            /* UpdateEntry() */
            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);
            }
         }
      }
   } while( (o = NOptimal) < TSIZE - 1 );


   for(o = 1; o < argc; o++)
   {
      PutD("%d = ", n = atoi(argv[o]));
      if( n < 0 )
      {
         PutC((int)'-');
         PutC((int)'(');
         Decompose(-n);
         PutC((int)')');
      }
      else
      {
         Decompose(n);
      }
      PutC((int)'\n');
   }

   return 0;
}