#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>
#include <assert.h>

FILE *fp;

typedef enum {
  BEGIN_T, END_T, LOOP_T, OP_T, INT_T, N_T, NONE_T
} tok;

int int_value;

int *npoly (void)
{
  int i;
  int *p = malloc (sizeof(int)*42);

  memset (p, 0, sizeof(int)*42);

  return p;
}

int *multpoly_const (int *p1, int c)
{
  int i;
  for (i = 0; i<42; ++i)
    p1[i] *= c;
  return p1;
}

int *multpoly_n (int *p)
{
  int i;
  for (i = 42; i>=1; --i)
    p[i] = p[i-1];
  p[0] = 0;
  return p;
}

int *addpoly_poly (int *p1, int *p2)
{
  int i;
  for (i = 0; i < 42; ++i)
    p1[i] += p2[i];
  return p1;
}

int *addpoly_const (int *p1, int c)
{
  p1[0] += c;
  return p1;
}

tok the_tok = NONE_T;

tok scan_new();
tok scan_lk();
void eat();
int *statement ();
int *statement_list();
int *prog ();

tok scan_lk ()
{
  if (the_tok == NONE_T)
    the_tok = scan_new();
  return the_tok;
}

void eat ()
{
  the_tok = NONE_T;
}

tok scan ()
{
  tok t = scan_lk();
  eat();
  return t;
}

tok scan_new ()
{
  int c, nskip;
  tok t;

  while ((c = fgetc(fp)) != EOF && isspace (c))
    ;

  assert (c != EOF);

  if (isdigit (c)) {
    char buf[10000], *cp = buf;

    *cp++ = c;

    while ((c = fgetc(fp)) != EOF && isdigit (c))
      *cp++ = c;
    *cp = 0;
    int_value = atoi (buf);
    return INT_T;
  }
  switch (c) {
  case 'B':
    t = BEGIN_T;
    nskip = 4;
    break;

  case 'E':
    t = END_T;
    nskip = 2;
    break;

  case 'L':
    t = LOOP_T;
    nskip = 3;
    break;

  case 'O':
    t = OP_T;
    nskip = 1;
    break;

  case 'n':
    return N_T;

  default:
    assert(0);
  }

  while (--nskip >= 0)
    fgetc (fp);

  return t;
}

int *statement_list ()
{
  int *res = statement ();
  
  while (1) {
    tok t = scan_lk();
    if (t == END_T) {
      return res;
    }
    res = addpoly_poly (res, statement());
  }
  return res;
}

int *statement ()
{
  tok t;
  int val, *res = npoly();

  switch (scan()) {
  case OP_T:
    assert (scan() == INT_T);
    return addpoly_const (res, int_value);

  case LOOP_T:
    t = scan ();
    if (t == N_T) {
      res = statement_list ();
      res = multpoly_n (res);
    } else {
      assert (t == INT_T);
      val = int_value;
      res = statement_list ();
      res = multpoly_const (res, val);
    }
    assert (scan() == END_T);
    return res;

  default:
    assert (0);
  }
}

int *prog ()
{
  int *res;
  assert (scan() == BEGIN_T);
  res = statement_list();
  assert (scan() == END_T);
  return res;
}

int main (void)
{
  char buf[2000];
  int nprog, k, i, j, *ex;
  fp = fopen ("complex.in", "r");
  
  fgets (buf, 2000, fp);
  nprog = atoi (buf);

  for (j=1;j<=nprog;++j) {
    printf ("Program #%d\n", j);
    printf ("Runtime = ");

    ex = prog ();

    for (i=41, k=0; i>=0; i--) {
      if (ex[i]==0) continue;
      if (k) printf ("+"); k++;
      if (ex[i] != 1) printf ("%d", ex[i]);
      if (ex[i] != 1 && i) printf ("*");
      if (i) printf ("n");
      if (i>1) printf ("^%d", i);
    }
    if (!k) printf ("0");
    printf ("\n\n");
  }
  return 0;
}